Tarjan's strongly connected components algorithm: Difference between revisions

Revision as of 03:02, 7 April 2024

Revision as of 08:19, 4 May 2024

Line 86:

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

This maycan be done, foras example,in bythe storingpseudocode above: store 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 journal|last=Nuutila|first=Esko|title=On Finding the Strongly Connected Components in a Directed Graph|journal=Information Processing Letters|pages=9–14|volume=49|number=1|doi=10.1016/0020-0190(94)90047-7|year=1994}}</ref><ref>{{cite journal|last=Pearce|first=David|title=A Space Efficient Algorithm for Detecting Strongly Connected Components|journal=Information Processing Letters|pages=47–52|number=1|volume=116|doi=10.1016/j.ipl.2015.08.010}}</ref>