Tarjan's strongly connected components algorithm: Difference between revisions

Revision as of 08:05, 6 February 2008

Revision as of 12:24, 27 February 2008

Line 36:

== Remarks ==

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