Reputation: 53
The strongly connected component algorithm from my book:
strongly-connected-component(G)
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
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