Revision as of 20:32, 24 October 2007 edit 216.142.162.99 (talk) →The Algorithm in pseudocode ← Previous edit		Revision as of 12:23, 4 November 2007 edit undo 88.96.19.134 (talk) →The Root Property: v'.dfs should read v'.index in the v.lowlink property Next edit →
Line 8: == The Root Property == 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'.~~dfs~~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]] ==

Tarjan's strongly connected components algorithm: Difference between revisions