Tarjan's strongly connected components algorithm: Difference between revisions

Revision as of 16:22, 29 May 2019

Revision as of 04:39, 25 July 2019

Line 92:

This may be done, for example, by storing a flag on each node that indicates whether it is on the stack, and performing this test by examining the flag.

''Space Complexity'': The Tarjan procedure requires two words of supplementary data per vertex for the <code>index</code> and <code>lowlink</code> fields, along with one bit for <code>onStack</code> and another for determining when <code>index</code> is undefined. In addition, one word is required on each stack frame to hold <code>v</code> and another for the current position in the edge list. Finally, the worst-case size of the stack <code>S</code> must be <math>|V|</math> (i.e. when the graph is one giant component). This gives a final analysis of <math>O(|V|\cdot(2+5w))</math> where <math>w</math> is the machine word size. The variation of Nuutila and Soisalon-Soininen reduced this to <math>O(|V|\cdot(1+4w))</math> and, subsequently, that of Pearce requires only <math>O(|V|\cdot(1+3w))</math>.<ref>{{cite webjournal|last=Nuutila|first=Esko|title=On Finding the Strongly Connected Components in a Directed Graph|url=https://doi.org/10.1016/0020-0190(94)90047-7|journal=Information Processing Letters|pages=9-149–14|volume=49|number=1|accessdatedoi=13 December 201710.1016/0020-0190(94)90047-7|year=1994}}</ref><ref>{{cite webjournal|last=Pearce|first=David|title=A Space Efficient Algorithm for Detecting Strongly Connected Components|url=https://doi.org/10.1016/j.ipl.2015.08.010|journal=Information Processing Letters|pages=47-5247–52|number=1|volume=116|accessdatedoi=13 December 201710.1016/j.ipl.2015.08.010}}</ref>

==Additional remarks==

Line 98:

[[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>

He also wrote:<ref>{{cite webbook|last=Knuth|first=Donald|title=Twenty Questions for Donald Knuth|url=http://www.informit.com/articles/article.aspx?p=2213858&WT.mc_id=Author_Knuth_20Questions|date=2014-05-20}}</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 ==