Question: Run the strongly connected components algorithm on the following directed graph G. When doing DFS on GR: whenever there is a choice of vertices to

Run the strongly connected components algorithm on the following directed graph G. When doing DFS on GR: whenever there is a choice of vertices to explore, always pick the one that is alphabetically first A: B, D B:C,D,E C:F D:E E : A,C F: I,J G: A, D, A H : D,E,G,I I: J J:C K: H In each case answer the following questions. (6.25 points each) (a) In what order are the strongly connected components (SCCs) found? (b) Which are source SCCs and which are sink SCCs? (c) Draw the "metagraph" (each meta-node is an SCC of G) (d) What is the minimum number of edges you must add to this graph to make it strongly connected
Step by Step Solution
There are 3 Steps involved in it
Get step-by-step solutions from verified subject matter experts
