How do I learn Tarjan's algorithm?

StackOverflow https://stackoverflow.com/questions/11010881

Question

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?

Was it helpful?

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.

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

OTHER TIPS

just adding to pjotr's answer: v.lowlink is basically the index of the upmost node that you have found in the tree. Keep in mind that upmost in this context means minimum as you keep increasing indices as you walk down. Now after processing all your successors, there's basically three cases:

  1. v.lowlink < v.index: This indicates that you have found a back edge. Note that we haven't just found any back edge, but one that points to a node that is "above" the current one. That's what v.lowlink < v.index implies.

  2. v.lowlink = v.index: What we know in this case is that there is no back edge referring to anything above the current node. There might be a back edge to this node (which means that one of your successor nodes w has a lowlink such that w.lowlink = v.lowlink = v.index). It could also be that there was a back edge referring to something below the current node, which means that there was a strongly-connected component below the current node that has been printed out already. The current node, however, is definitely the root of a strongly-connected component as well.

  3. v.lowlink > v.index: That's actually not possible. I'm just listing it for the sake of completeness. ;)

Hope it helps!

Some Intuition about the Tarjan's Algorithm:

  • During DFS, when we encounter a back edge from vertex v, we update its lowest reachable ancestor i.e. we update the value of low[v]

  • Now when the all the outgoing edges of a vertex are processed i.e we are about to exit the DFS call for the vertex v, we check the value of low[v], whether low[v] == v (Explanation below). If not this means v is not the root of the SCC and we now give the benefit to the parent of v i.e. the lowest reachable ancestor of parent[v] is now changed to low[v].

This sounds logical as if although there is no direct back edge from the parent[v] to the ancestor of v, but there is a path (back edge of v + edge towards v) via which the parent[v] can still reach the ancestor of v. Thus we have also updated the low[parent[v]] here. Therefore, we will keep on updating this chain and low[v] for all v will keep on updating until, we reach to the ancestor (via backtracking). For this ancestor low[v] will be equal to v. And thus this will act as the root of the SCC.

Hope this helps

Path for Mastering Bridges and Articulation Algorithms

Licensed under: CC-BY-SA with attribution
Not affiliated with StackOverflow
scroll top