Tarjan's strongly connected components algorithm: Difference between revisions

Revision as of 22:23, 21 January 2009

Revision as of 02:38, 31 January 2009

Line 11:

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

forall v in V do

tarjan(v0) // Start a DFS at the start node

if (v.index is undefined) // Start a DFS at each node

tarjan(v0v) // Start a DFS atwe thehaven't startvisited nodeyet

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) or // Was successorIgnore v'already visited?found SCCs

tarjan( v') is in // RecurseS)

if (v'.index is undefined) // Was successor v' visited?

tarjan(v') // Recurse

v.lowlink = min(v.lowlink, v'.lowlink)

if (v.lowlink == v.index) // Is v the root of an SCC?

elseif (number[v'] < number[v])

v.lowlink = min(v.lowlink, v'.number)

if (v.lowlink == v.index) // Is v the root of an SCC?

print "SCC:"

repeat