korkotyan
korkotyan

Reputation: 53

I can not really understand how the strongly connected component algorithm works

The strongly connected component algorithm from my book:

strongly-connected-component(G)

  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 line 1)
  4. output the vertices of each tree in the depth-first forest of step 3 as a separate strong connected component

I do not really understand how line 4 works, how the algorithm makes the forest from the DFS on the transpose graph. I do understand why to call both times to DFS.

Thanks for any help.

Upvotes: 2

Views: 439

Answers (1)

David Eisenstat
David Eisenstat

Reputation: 65458

The DFS main loop calls a recursive helper function on each vertex to explore the vertices reachable from that vertex. A "tree" here is the set of vertices newly visited by one of these recursive calls. The helper function must be modified to construct this set, which is a strong component whenever it is nonempty.

Upvotes: 2

Related Questions