Tarjan's strongly connected components algorithm: Difference between revisions

Revision as of 12:24, 27 February 2008

Revision as of 21:22, 4 March 2008

Line 4:

The basic idea of the algorithm is this: a [[depth-first search]] begins from a start node. The strongly connected components form the subtrees of the search tree, the roots of which are the roots of the strongly connected components.

The nodes are placed on a [[Stack (data structure)|stack]] in the order in which they are visited. When the search returns from a subtree, the nodes are taken from the stack and it is determined whether each node is the root of a strongly connected component. If a node is the root of a strongly connected component, then it and all of the nodes taken off before it formfrom that strongly connected component.

== The Root Property ==