Tarjan's strongly connected components algorithm: Difference between revisions

Revision as of 17:16, 7 June 2009

Revision as of 18:57, 7 June 2009

Line 1:

'''Tarjan's Algorithm''' (named for its discoverer, [[Robert Tarjan]]) is a [[graph theory]] [[algorithm]] for finding the [[strongly connected components]] of a [[Graph (data structure)|graph]]. Although it precedes it chronologically, it can be seen as an improved version of [[Kosaraju's algorithm|Kosaraju's algorithm]], and is comparable in efficiency to [[Gabow's algorithm]].

== Idea ==

Line 10:

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 algorithm in [[pseudocode]] ==

<pre>Input: Graph G = (V, E)

Line 46:

== External links ==

*[http://www.ics.uci.edu/~eppstein/161/960220.html#sca Description of Tarjan's Algorithm]<br>

*[http://algowiki.net/wiki/index.php/Tarjan%27s_algorithm Implementation of Tarjan's Algorithm in Java]