Content deleted Content added
Add link to implementation of algorithm in Go |
Add further information about the space complexity of Tarjan's algorithm, including references to variations which further reduce its requirements. |
||
Line 84:
== Complexity ==
''Time 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>.
In order to achieve this complexity, the test for whether <tt>w</tt> is on the stack should be done in constant time.
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(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(1+4w))</math> and, subsequently, that of Pearce requires only <math>O(v(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/0020-0190(94)90047-7|journal=Information Processing Letters|pages=47-52|number=1|volume=116|accessdate=13 December 2017}}</ref>
==Additional remarks==
| |||