Tarjan's strongly connected components algorithm: Difference between revisions

Revision as of 20:19, 13 October 2008

Revision as of 20:20, 13 October 2008

Line 11:

The algorithm in [[pseudocode]]

The algorithm in [[pseudocode]]

Input: Graph G = (V, E), Start node v0 index = 0 //

DFS node number counter S = empty //

An Input: emptyGraph stackG of= nodes tarjan(v0V, E), Start node v0 index = 0 //

Start DFS anode DFSnumber atcounter theS = empty start node procedure tarjan(v) v.index = index //

SetAn theempty stack of nodes tarjan(v0) depth index for v v.lowlink = index index = index + 1 S.push(v) //

PushStart va onDFS at the stackstart forallnode procedure tarjan(v,) v').index = index in E do //

Set the depth index for v v.lowlink = index index = index + 1 S.push(v)

Consider successors of v if (v'.index is undefined) //

Was successorPush v' visited?on the stack forall tarjan(v, v') in E do //

Consider successors of v if (v'.index is undefined) //

Recurse v.lowlink = min(v.lowlink, v'.lowlink) elseif (v' in S) //

Was successor v' visited? tarjan(v')

Is v' on the stack? v.lowlink = min(v.lowlink, v'.lowlink) if (v.lowlink == v.index) //

Recurse v.lowlink = min(v.lowlink, v'.lowlink) elseif (v' in S) //

Is v the root of an SCC? print "SCC:" repeat v' = S.pop print v' until (v' == v)</span> == L'algorithme de [[pseudocode]]

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]]

== Remarks ==