Content deleted Content added
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]]
Input: Graph G = (V, E), Start node v0 index = 0
DFS node number counter S = empty
An empty stack of nodes tarjan(v0)
Start a DFS at the start node procedure tarjan(v) v.index = index
Set the depth index for v v.lowlink = index index = index + 1 S.push(v)
Push v on the stack forall (v, v') in E do
Consider successors of v if (v'.index is undefined)
Was successor v' visited? tarjan(v')
Recurse v.lowlink = min(v.lowlink, v'.lowlink) elseif (v' in S)
Is v' on the stack? v.lowlink = min(v.lowlink, v'.lowlink) if (v.lowlink == v.index)
Is v the root of an SCC? print "SCC:" repeat v' = S.pop print v' until (v' == v) [[pseudocode]]
== Remarks ==
| |||