Tarjan's strongly connected components algorithm: Difference between revisions

Revision as of 10:19, 6 January 2018

Revision as of 20:31, 19 February 2018

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 <tt>index</tt> and <tt>lowlink</tt> fields, along with one bit for <tt>onStack</tt> and another for determining when <tt>index</tt> is undefined. In addition, one word is required on each stack frame to hold <tt>v</tt> and another for the current position in the edge list. Finally, the worst-case size of the stack <tt>S</tt> must be <math>|V|</math> (i.e. when the graph is one giant component). This gives a final analysis of <math>O(v|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|V|\cdot(1+4w))</math> and, subsequently, that of Pearce requires only <math>O(v|V|\cdot(1+3w))</math>.<ref>{{cite web|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-14|volume=49|number=1|accessdate=13 December 2017}}</ref><ref>{{cite web|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-52|number=1|volume=116|accessdate=13 December 2017}}</ref>

==Additional remarks==