Tarjan's strongly connected components algorithm: Difference between revisions

Revision as of 02:38, 31 January 2009

Revision as of 02:39, 31 January 2009

Line 40:

#Complexity: The tarjan 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 (O(|V|+|E|)).

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

#The algorithm can only find those strongly connected components that are reachable from the start node. This can be overcome by starting the algorithm several times from different start nodes.

== Literature ==