Assignment代写-Algorithm Assignment 5
2019-10-20
Problem 1.(17 points) In performing search of a graph we get a tree where atree edge(u, v) indicates thatvhas not been visited when we examine this edge while we visitu. We have the following 3 types of non-tree edges: (a)back edge(u, v) is a non-tree edge such thatvis an ancestor ofuin the tree discovered when we visitu, (b)forward edge(u, v) is a non-tree edge such thatvis a descendant ofu discovered when we visitu, (c)cross edge(u, v) is a non-tree edge such that vis neither a descendant of nor an ancestor ofudiscovered when we visitu. (a) Show the DFS and BFS tree of the following directed graph starting from vertexv 1 showing clearly the tree edges and for non-tree edges mark them as one of the above 3 types (back,forward,cross).Assume that vertices in the ad- jaceny list of a vertex are stored in increasing order of its indices.(11 points)