I am trying self-study Graph Theory, and now trying to understand how to find SCC in a graph. I have read several different questions/answers on SO (e.g., 1,2,3,4,5,6,7,8), but I cant find one with a complete step-by-step example I could follow.
According to CORMEN (Introduction to Algorithms), one method is:
- Call DFS(G) to compute finishing times f[u] for each vertex u
- Compute Transpose(G)
- Call DFS(Transpose(G)), but in the main loop of DFS, consider the vertices in order of decreasing f[u] (as computed in step 1)
- Output the vertices of each tree in the depth-first forest of step 3 as a separate strong connected component
Observe the following graph (question is 3.4 from here. I have found several solutions here and here, but I am trying to break this down and understand it myself.)
Step 1: Call DFS(G) to compute finishing times f[u] for each vertex u
Running DFS starting on vertex A:
Please notice RED text formatted as [Pre-Vist, Post-Visit]
Step 2: Compute Transpose(G)
Step 3. Call DFS(Transpose(G)), but in the main loop of DFS, consider the vertices in order of decreasing f[u] (as computed in step 1)
Okay, so vertices in order of decreasing post-visit(finishing times) values:
{E, B, A, H, G, I , C, D, F ,J}
So at this step, we run DFS on G^T but start with each vertex from above list:
Step 4: Output the vertices of each tree in the depth-first forest of step 3 as a separate strong connected component.
So we have five strongly connected components: {E}, {B}, {A}, {H, I, G}, {C, J, F, D}
Your steps are correct and your answer is also correct, by examining the other answers you provided you can see that they used a different algorithm: First you run DFS on G transposed and then you run an undirected components algorithm on G processing the vertices in decreasing order of their post numbers from the previous step.
The problem is they ran this last step on G transposed instead of in G and thus got an incorrent answer. If you read Dasgupta from page 98 onwards you will see a detailed explanation of the algorithm they (tried) to use.