graphdepth-first-searchtarjans-algorithm

How do I learn Tarjan's algorithm?


I have been trying to learn Tarjan's algorithm from Wikipedia for 3 hours now, but I just can't make head or tail of it. :(

http://en.wikipedia.org/wiki/Tarjan's_strongly_connected_components_algorithm#cite_note-1

Why is it a subtree of the DFS tree? (actually DFS produces a forest? o_O) And why does v.lowlink=v.index imply that v is a root?

Can someone please explain this to me / give the intuition or motivation behind this algorithm?


Solution

  • The idea is: When traversing the tree, every time you've searched through a branch and are backtracking, you check whether you've encountered an edge to an 'upper' node in the tree.

    DFS produces a forest, but you always consider one tree a time. An SCC is always included in one DFS tree, otherwise (being an SCC) there would be a path in both directions between both (all) trees in question - that's a contradiction.