Tarjan's strongly connected components algorithm: Difference between revisions

Revision as of 18:57, 7 June 2009

Revision as of 13:04, 27 August 2009

Line 39:

== 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, ie <math>O(|V|+|E|)</math>.

# 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.