Tarjan's strongly connected components algorithm

Tarjan 's algorithm ( according to its inventor Robert Tarjan ) is used in graph theory to determine the strongly connected components ( SZKn ) of a directed graph.

Idea

The basic idea of the algorithm is, starting from a start node to perform a depth-first search in the graph. The strongly connected components ( SZKn ) case form subtrees of depth-first search tree, the roots of these trees are called roots of the connected components.

The nodes are stored in the order in which they will be visited on a stack. Reverses the depth-first search back from a sub-tree, the nodes are removed and re-issued from the stack, each time it is decided whether the node is the root of a connected component. If so, the algorithm indicates that the previously issued nodes form a SZK.

The root property

Apparently for the algorithm is crucial that when you return from a sub- tree for each node can be determined whether it is the root of a connected component. To this end, each node v is v.dfs next to the depth-first index, which numbered the nodes in the order in which they are "discovered" in the depth-first search, a value assigned v.lowlink, where

It now applies: v is the root of a connected component if and only if is v.lowlink = v.dfs. v.lowlink can be calculated during the depth-first search so that the value is known at the time of the query.

Visualization

The algorithm in pseudocode

Input: Graph G = (V, E) maxdfs: = 0 / / counter for dfs U: = V / / set of unvisited nodes S: = { } / / stack is empty at the beginning while ( there is a v0 in U) do / / As long as there is as yet unreachable nodes    Tarjan (v0 ) / / call works of all reachable nodes from v0 end while Tarjan procedure (V) v.dfs: = maxdfs; / / Set depth-first index v.lowlink: = maxdfs; / / V.lowlink < = v.dfs maxdfs: = maxdfs 1; / Increase / Counter S.push (v ); / / Set v to Stack U: = U \ {v }; / / Remove v from U consider forall (v, v ') in E do / / adjacent nodes    if ( v ' U )      Tarjan (v '); / / Recursive call      v.lowlink: = min ( v.lowlink, v ' lowlink. );    / / Query whether v ' is in the stack.    / / With a clever implementation in O (1).    / / (Eg setting a bit in the node with the "push " and " pop" )    elseif (v ' in S)      v.lowlink: = min ( v.lowlink, v ' dfs. );    end if end for if ( v.lowlink = v.dfs ) / / root of a SCC    print " SZK ";    repeat      v ': = S.pop;      print v ';    until ( v ' = v ); end if Comments