Tarjan's strongly connected components algorithm: Difference between revisions

Revision as of 21:02, 9 October 2008

Revision as of 03:19, 13 October 2008

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.

<span onmouseover="_tipon(this)" onmouseout="_tipoff()"><span class="google-src-text" style="direction: ltr; text-align: left">== 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)</span> == L'algorithme de [[pseudocode]] == Entrée: Graphique G = (V, E), nœud de début v0 index = 0 / / DFS numéro de noeud contre S = vide / / Une pile vide de noeuds Tarjan (v0) / / Démarrer un DFS au début noeud procédure Tarjan (v) = indice v.index / / Définit la profondeur indice v.lowlink pour v = index index = index + 1 S.push (v) / / Push v sur la pile forall (v, v ') en ne E / / Examiner successeurs de v si (v'. indice est indéfini) / / v successeur a été «visitée? Tarjan (v ') / / RECURSE v.lowlink = min (v.lowlink, v '. lowlink) elseif (V' dans S) / / Est-v 'sur la pile? v.lowlink = min (v.lowlink, v'. lowlink) si (v.lowlink == v.index) / / Est v la racine d'un CCN? print "CSC:" répéter v '= v S.pop imprimer "jusqu'à ce que (v' == v)</span>

== 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)

== Remarks ==