Answer Happy

3 h m 7 k 6.0 4 3 f b L Depth-First Search and Breadth-First Search (85 points) 1. (10 points) From the above graph, construct a. a weighted adjacency list and b. a weighted adjacency matrix for the graph of Figure 1. 2. (40 points) Traversing the graph based on its weighted adjacency list representation obtained in problem (1). construct its depth-first search tree forest starting from the vertex a. In your obtained DFS tree forest, show the tree edges (indicated as solid line) and back edges (indicated as dotted line) for your trees. Traversal's stack contains symbols (such as Vix, the first subscript number i indicates that the order in which a vertex V was first visited (i.c., the order for pushing V onto the stack, counting 0<i< n); the second one indicates the order in which it became a dead-end (i.e., the order for popping off V from the stack, counting 0<k≤n). For this problem, you need to give your: (a) Traversal's stack with time-stamp. (b) The corresponding depth-first search (DFS) tree forest, with indications of tree edges and back edges. (c) The DFS yields orderings of vertices; what are they? (d) Is this graph connected? (e) Is this graph acyclic? (f) Does the graph have articulation points? and (h) What is the topological sort ordering for the graph? (1) What are the time efficiency and space efficiency of the DFS? Figure 1.