Tarjan's strongly connected components algorithm: Difference between revisions

Revision as of 22:21, 30 September 2007

Revision as of 23:33, 30 September 2007

Line 17:

S := {} // An initially empty stack

tarjan(v0) // Call the function with the start node

''procedure tarjan''(v)

v.dfs := max_dfs; // Set the depth index for v

v.lowlink := max_dfs; // v.lowlink <:= v.dfsmax_dfs

max_dfs := max_dfs + 1; // Increment the counter

S.push(v); // PlacePush v on the stack

U := U \ {v}; // SeparateRemove v from the unvisited nodes U

forall (v, v') in E do // Consider thesuccessors neighboringof v nodes

if (v' in U) // Is successor v' unvisited?

tarjan(v'); // recursive callRecurse

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

// Ask whetherelseif (v' isin S) // Is v' on the stack ?

v.lowlink := min(v.lowlink, v'.dfs);

// by a clever constant time method

//if (forv.lowlink example,= settingv.dfs) a flag on the node// whenIs itv is pushedthe orroot popped)of an SCC?

elseif (v' inprint S)"SCC:"

repeat

v.lowlink := min(v.lowlink, v'.dfs);

v' := S.pop;

end if

print v';

end for

until (v' = v);

if (v.lowlink = v.dfs) // the root of a strongly connected component

print "SZK:";

repeat

v' := S.pop;

print v';

until (v' = v);

end if

== Remarks ==

#Complexity: The tarjanTarjan procedure is called once for each node; the forall statement considers each edge at most twice. The algorithm's running time is therefore linear in the number of edges in G.

#The test for whether v' is on the stack should be done in constant time, for example, by testing a flag stored on each node that indicates whether it is on the stack.

#Naturally, theThe algorithm can only find those strongly connected components that are reachable from the start node. Otherwise,This thecan algorithmbe mustovercome beby startedstarting the algorithm several times from different start nodes.

== Literature ==