Tarjan's strongly connected components algorithm: Difference between revisions

Revision as of 13:35, 24 June 2016

Revision as of 23:31, 17 July 2016

Line 81:

When each node finishes recursing, if its lowlink is still set to its index, then it is the root node of a strongly connected component, formed by all of the nodes above it on the stack. The algorithm pops the stack up to and including the current node, and presents all of these nodes as a strongly connected component.

== RemarksComplexity ==

# Complexity: The Tarjan procedure is called once for each node; the forall statement considers each edge at most once. The algorithm's running time is therefore linear in the number of edges and nodes in G, i.e. <math>O(|V|+|E|)</math>.

# The test for whether <tt>w</tt> 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.

In order to achieve this complexity, the test for whether <tt>w</tt> is on the stack should be done in constant time.

# While there is nothing special about the order of the nodes within each strongly connected component, one useful property of the algorithm is that no strongly connected component will be identified before any of its successors. Therefore, the order in which the strongly connected components are identified constitutes a reverse [[Topological sorting|topological sort]] of the [[Directed acyclic graph|DAG]] formed by the strongly connected components.<ref>{{cite web|last=Harrison|first=Paul|title=Robust topological sorting and Tarjan's algorithm in Python|url=http://www.logarithmic.net/pfh/blog/01208083168|accessdate=9 February 2011}}</ref>

#This The test for whether <tt>w</tt> is on the stack shouldmay be done in constant time, for example, by testingstoring a flag stored on each node that indicates whether it is on the stack., and performing this test by examining the flag.

# Tarjan's algorithm was mentioned as one of his favorite implementations by Knuth appearing in his book The Stanford GraphBase, pages 512–519. He considered this as one of the most beautiful algorithms with a quote <ref>{{cite web|last=Harrison|first=Knuth|title=Twenty Questions for Donald Knuth|url=http://www.informit.com/articles/article.aspx?p=2213858&WT.mc_id=Author_Knuth_20Questions}}</ref> {{quote|The data structures that he devised for this problem fit together in an amazingly beautiful way, so that the quantities you need to look at while exploring a directed graph are always magically at your fingertips. And his algorithm also does topological sorting as a byproduct.}}

==Additional remarks==

# While there is nothing special about the order of the nodes within each strongly connected component, one useful property of the algorithm is that no strongly connected component will be identified before any of its successors. Therefore, the order in which the strongly connected components are identified constitutes a reverse [[Topological sorting|topological sort]] of the [[Directed acyclic graph|DAG]] formed by the strongly connected components.<ref>{{cite web|last=Harrison|first=Paul|title=Robust topological sorting and Tarjan's algorithm in Python|url=http://www.logarithmic.net/pfh/blog/01208083168|accessdate=9 February 2011}}</ref>

[[Donald Knuth]] described Tarjan's algorithm as one of Knuth's favorite implementations in his book ''The Stanford GraphBase''.<ref>Knuth, ''The Stanford GraphBase'', pages 512–519.</ref>

# Tarjan's algorithm was mentioned as one of his favorite implementations by Knuth appearing in his book The Stanford GraphBase, pages 512–519. He considered this as one of the most beautiful algorithms with aalso quotewrote: <ref>{{cite web|last=Harrison|first=Knuth|title=Twenty Questions for Donald Knuth|url=http://www.informit.com/articles/article.aspx?p=2213858&WT.mc_id=Author_Knuth_20Questions}}</ref> {{quote|The data structures that he devised for this problem fit together in an amazingly beautiful way, so that the quantities you need to look at while exploring a directed graph are always magically at your fingertips. And his algorithm also does topological sorting as a byproduct.}}

== References ==