How do I learn Tarjan's algorithm?

graph depth-first-search tarjans-algorithm
Nihal picture Nihal · Jun 13, 2012 · Viewed 14.3k times · Source

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?

Answer

voidengine picture voidengine · Jun 13, 2012

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.

  • If you didn't (if (v.lowlink = v.index)), then you've just completed an SCC - it consists of the current node and all nodes on the stack. That's exactly a subtree of the DFS tree, except for the nodes in SCCs that were already completed.

  • If you did, you propagate this information to 'upper' nodes (v.lowlink := min(v.lowlink, w.lowlink)), because combined with the path in DFS tree the edge creates an 'upward' path.

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.

Related questions

Explanation of runtimes of BFS and DFS

Why are the running times of BFS and DFS O(V+E), especially when there is a node that has a directed edge to a node that can be reached from the vertex, like in this example in the following …

Read More
Detecting cycles in a graph using DFS: 2 different approaches and what's the difference

Note that a graph is represented as an adjacency list. I've heard of 2 approaches to find a cycle in a graph: Keep an array of boolean values to keep track of whether you visited a node before. If you run …

Read More
How to implement depth first search for graph with a non-recursive approach

I have spent lots of time on this issue. However, I can only find solutions with non-recursive methods for a tree: Non recursive for tree, or a recursive method for the graph, Recursive for graph. And lots of tutorials (I …

Read More