Tarjan's strongly connected components algorithm: Difference between revisions

Revision as of 21:22, 4 March 2008

Revision as of 07:37, 31 March 2008

Line 6:

The nodes are placed on a [[Stack (data structure)|stack]] in the order in which they are visited. When the search returns from a subtree, the nodes are taken from the stack and it is determined whether each node is the root of a strongly connected component. If a node is the root of a strongly connected component, then it and all of the nodes taken off before it form that strongly connected component.

== The Rootroot Propertyproperty ==

The crux of the algorithm comes in determining whether a node is the root of a strongly connected component. To do this, each node is given a depth search index <tt>v.index</tt>, which numbers the nodes consecutively in the order in which they are discovered. In addition, each node is assigned a value <tt>v.lowlink</tt> that satisfies <tt>v.lowlink := min {v'.index: v' is reachable from v}</tt>. Therefore <tt>v</tt> is the root of a strongly connected component if and only if <tt>v.lowlink = v.index</tt>. The value <tt>v.lowlink</tt> is computed during the depth first search such that it is always known when needed.

== The Algorithmalgorithm in [[pseudocode]] ==

Input: Graph G = (V, E), Start node v0