Solution Found!
Run the strongly connected components algorithm on the following directed graphs G
Chapter 3, Problem 3.4(choose chapter or problem)
Run the strongly connected components algorithm on the following directed graphs G. When Doing DFS on \(G^{R}\): whenever there is a choice of vertices to explore, always pick the one that is alphabetically first.
In each case answer the following questions.
(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?
Questions & Answers
QUESTION:
Run the strongly connected components algorithm on the following directed graphs G. When Doing DFS on \(G^{R}\): whenever there is a choice of vertices to explore, always pick the one that is alphabetically first.
In each case answer the following questions.
(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?
ANSWER:Step 1 of 4
We have the algorithm of strongly connected components as follows.
1. Run depth-first search on \(G^{R}\).
2. Run the undirected connected components algorithm on G, and during the depth-first search, process the vertices in decreasing order of their post numbers from step 1.
The approach involves identifying, for each vertex i that is not part of any strongly connected component, the vertices that belong to the strongly connected component containing vertex i. Two vertices, i and j, will be considered part of the same strongly connected component if there exists a directed path from vertex i to vertex j and vice versa.
(a)
Given two graphs, we have to find the order of strongly connected components in graphs
Graph i: The vertices HIG can be considered as a strongly connected component because there is a path between all three vertices. Similarly, CDFJ is also a strongly connected component because of the existence of a path between all four vertices. On the other hand, vertex A, B, and E are not connected to any other vertex. Although, vertex B has a path to A, vice-versa is not true. So, apart from HIG and CDFJ, the graph has three other connected components with only one vertex E, B, and A.
Strongly connected components of graph i are E, B, A, HIG, and CDFJ.
Graph ii:
Strongly connected components of graph ii are ABE, C, and DHGFI. While running the topological sorting algorithm of \(G^{R}\), we got the list in decreasing order of post numbers DGHIFCAEB.