Search code examples
algorithmgraph-theorystrongly-connected-graph

How to find Strongly Connected Components in a Graph?

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:

  1. Call DFS(G) to compute finishing times f[u] for each vertex u
  2. Compute Transpose(G)
  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)
  4. 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.)

enter image description here

Step 1: Call DFS(G) to compute finishing times f[u] for each vertex u

Running DFS starting on vertex A:

enter image description here

Please notice RED text formatted as [Pre-Vist, Post-Visit]

Step 2: Compute Transpose(G)

enter image description here

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:

  • DFS(E): {E}
  • DFS(B): {B}
  • DFS(A): {A}
  • DFS(H): {H, I, G}
  • DFS(G): remove from list since it is already visited
  • DFS(I): remove from list since it is already visited
  • DFS(C): {C, J, F, D}
  • DFS(J): remove from list since it is already visited
  • DFS(F): remove from list since it is already visited
  • DFS(D): remove from list since it is already visited

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}

This is what I believe is correct. However, solutions I found here and here say SCCs are {C,J,F,H,I,G,D}, and {A,E,B}. Where are my mistakes?

Solution

  • 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.