What if I do not use G transpose in calculating Strongly Connected Components?

Question

I am reading Introduction to Algorithms. In 22.5 Strongly Connected Component, the algorithm STRONGLY-CONNECTED-COMPONENT(G) is defined as:

1. Call DFS(G) to compute finishing times u.f for each vertex u
2. Compute G transpose
3. Call DFS(G transpose), but in the main loop of DFS, consider the vertices in order of decreasing u.f(as computed in line 1)
4. Output the vertices of each tree in the depth-first forest formed in line 3 as a separate strongly connected component

If I change the alogrithm to just using G, without calculating G transpose. Also consider the vertices in order of Increasing u.f(Reverse order of topological sort):

1. Call DFS(G) to compute finishing times u.f for each vertex u
2. Call DFS(G), but in the main loop of DFS, consider the vertices in order of increasing u.f(as computed in line 1)
3. Output the vertices of each tree in the depth-first forest formed in line 2

Why is this algorithm wrong?

Heartbreaker

You question is better suited for cs.stackexchange.com – Des

Answer 1

Your question is actually exercise 22.5-3 in the book. A counter example to the correctness of your alternative algorithm is given here: http://sites.math.rutgers.edu/~ajl213/CLRS/Ch22.pdf

Professor Bacon’s suggestion doesn’t work out. As an example, suppose that our graph is on the three vertices {1, 2, 3} and consists of the edges (2, 1),(2, 3),(3, 2). Then, we should end up with {2, 3} and {1} as our SCC’s. However, a possible DFS starting at 2 could explore 3 before 1, this would mean that the finish time of 3 is lower than of 1 and 2. This means that when we first perform the DFS starting at 3. However, a DFS starting at 3 will be able to reach all other vertices. This means that the algorithm would return that the entire graph is a single SCC, even though this is clearly not the case since there is neither a path from 1 to 2 of from 1 to 3.

Gooden

Answer 2

The vertices in strongly connected component are, by definiton, connected to each other (by a path, not necessarily by direct edge). if you make first DFS call on vertex X, you find out "which vertices is X connected to" (X -> N). To make sure that all those vertices are connected to X (N -> X) and therefore validate strong connectivity you need to traverse the edges in reversed directions. The easiest way to do such is by transposing the graph.

If you look for proof of the algorithm, i am sure you will find some. It may not be the easiest to understand but check this source for example: Correctness of the algorithm for finding strongly connected components

Greatniece