Tarjan's strongly connected components algorithm: Difference between revisions

Revision as of 19:11, 9 April 2007

Revision as of 19:12, 9 April 2007

Line 8:

== The Root Property ==

The main crux of the algorithm is determining whether a node is in the root of a strongly connected component. For that purpose, each node is given a depth search index <tt>v.dfs</tt>, which numbers the nodes consecutively in the order in which they are "discovered" by the depth first search. In addition, a value <tt>v.lowlink</tt> is assigned, such that <tt>v.lowlink := min {v'.dfs: 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.dfs. v.lowlink</tt> can be computed during the depth first search in such a way that the value is known at the time of the query.

== The Algorithm in [[pseudocode]] ==