Question

10. (16) You will compute the strongly connected components of this graph in three steps. a. STRONGLY-CONNECTED-COMPONENTS (G) (7) Perform a depth-first search on call DFS(G) to compute finishing times w/ for each vertex the following graph. (To make 2 compute GT this easier to grade, everyone call DFS(GT), but in the main loop of DFS, consider the vertices in order of decreasing wf (as computed in line 1) please start with vertex "a" and 4 outout the vertices of each tree in the depth-first forest formed in line 3 as a process adjacent vertices in separate strongly connected component alphabetical order.) Label each vertex with its start and finish time (in the positions on the left and right of the vertices, respectively), and label each edge in the below it or next to it) as T for tree edge, B for back edge, C for cross edge, or F for forward b. (2) Write the vertices of the above graph from highest to lowest finish time obtained by the DFS. (This is a topological sort.) c. (7) Perform a second DFS on GT, the transpose graph (shown below), processing vertices in the order of finish times above to find the Strongly Connected Components of the graph. Label each node with its start and finish time and darken the tree edges. Then circle the components you found. Please check that you have filled in all fields, darkened the tree edges, and circled components. Students often loose points for merely not finishing the problem.

ignore red marks. Thanks

Answer 1

a.

DFS: Depth First Search: It goes as deep as possible and backtracks till all the vertices are visited

Edge Classification

T - Tree Edge
B - Back Edge
C - Cross Edge
F - Forward Edge

8.0

b. Topological Order: c b f e b d a

c. DFS of Transpose

,Ꭷ .© ,

d.

DES G oooooo A DES G Connected Components

Please up vote. Happy Learning!