Tarjan's strongly connected components algorithm: Difference between revisions

Revision as of 03:37, 15 April 2016

Revision as of 03:39, 15 April 2016

Line 23:

Nodes are placed on a [[Stack (data structure)|stack]] in the order in which they are visited. When the depth-first search recursively visits a node <tt>v</tt> and its descendants, those nodes are not all necessarily popped from the stack when this recursive call returns. The crucial [[Invariant (computer science)|invariant property]] is that a node remains on the stack after it has been visited if and only if there exists a path in the input graph from it to some node earlier on the stack.

At the end of the call that visits <tt>v</tt> and its descendants, we know whether <tt>v</tt> itself has a path to any node earlier on the stack. If so, the call returns, leaving <tt>v</tt> on the stack to preserve the invariant. If not, then <tt>v</tt> must be the root of its strongly connected component, which consists of <tt>v</tt> together with any nodes later on the stack than <tt>v</tt> (such nodes all have paths back to <tt>v</tt> but not to any earlier node, because if they had paths to earlier nodes then <tt>v</tt> would also have paths to earlier nodes which is false ). The This entirecomponent component rooted at <tt>v</tt> is then popped from the stack and returned, again preserving the invariant.

=== Bookkeeping ===