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