Path-based strong component algorithm

<h2 id="description">Description</h2>
The algorithm performs a depth-first search of the given graph G, maintaining as it does two stacks S and P (in addition to the normal call stack for a recursive function).
Stack S contains all the vertices that have not yet been assigned to a strongly connected component, in the order in which the depth-first search reaches the vertices.
Stack P contains vertices that have not yet been determined to belong to different strongly connected components from each other. It also uses a counter C of the number of vertices reached so far, which it uses to compute the preorder numbers of the vertices.
When the depth-first search reaches a vertex v, the algorithm performs the following steps:

<ol><li>Set the preorder number of v to C, and increment C.</li>
<li>Push v onto S and also onto P.</li>
<li>For each edge from v to a neighboring vertex w:
<ul><li>If the preorder number of w has not yet been assigned (the edge is a <a href="/facts/Depth-first_search/luxJKVph">tree edge</a>), recursively search w;</li>
<li>Otherwise, if w has not yet been assigned to a strongly connected component (the edge is a forward/back/cross edge):
<ul><li>Repeatedly pop vertices from P until the top element of P has a preorder number less than or equal to the preorder number of w.</li></ul></li></ul></li>
<li>If v is the top element of P:
<ul><li>Pop vertices from S until v has been popped, and assign the popped vertices to a new component.</li>
<li>Pop v from P.</li></ul></li></ol>
The overall algorithm consists of a loop through the vertices of the graph, calling this recursive search on each vertex that does not yet have a preorder number assigned to it.

<h2 id="related-algorithms">Related algorithms</h2>
Like this algorithm, <a href="/facts/Tarjan%2527s_strongly_connected_components_algorithm/N4e6cb6M">Tarjan's strongly connected components algorithm</a> also uses depth first search together with a stack to keep track of vertices that have not yet been assigned to a component, and moves these vertices into a new component when it finishes expanding the final vertex of its component. However, in place of the stack P, Tarjan's algorithm uses a vertex-indexed <a href="/facts/Array_(data_type)/gHJJ3XPw">array</a> of preorder numbers, assigned in the order that vertices are first visited in the <a href="/facts/Depth-first_search/luxJKVph">depth-first search</a>. The preorder array is used to keep track of when to form a new component.

<h2 id="notes">Notes</h2>

<ul><li>Cheriyan, J.; <a href="/facts/Kurt_Mehlhorn/jj3uWv49">Mehlhorn, K.</a> (1996), "Algorithms for dense graphs and networks on the random access computer", <a href="/facts/Algorithmica/EqSt27Q2">Algorithmica</a>, 15 (6): 521–549, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1007%2FBF01940880">10.1007/BF01940880</a>, <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:8930091">8930091</a>.</li>
<li><a href="/facts/Edsger_Dijkstra/910x0MjT">Dijkstra, Edsger</a> (1976), A Discipline of Programming, NJ: Prentice Hall, Ch. 25.</li>
<li><a href="/facts/Harold_N._Gabow/gLt88dfp">Gabow, Harold N.</a> (2000), <a href="https://www.cs.princeton.edu/courses/archive/spr04/cos423/handouts/path%20based...pdf">"Path-based depth-first search for strong and biconnected components"</a> (PDF), Information Processing Letters, 74 (3–4): 107–114, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1016%2FS0020-0190%2800%2900051-X">10.1016/S0020-0190(00)00051-X</a>, <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=1761551">1761551</a>.</li>
<li><a href="/facts/Ian_Munro_(computer_scientist)/JhnreJNK">Munro, Ian</a> (1971), "Efficient determination of the transitive closure of a directed graph", Information Processing Letters, 1 (2): 56–58, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1016%2F0020-0190%2871%2990006-8">10.1016/0020-0190(71)90006-8</a>.</li>
<li>Purdom, P. Jr. (1970), <a href="http://digital.library.wisc.edu/1793/57514">"A transitive closure algorithm"</a>, BIT, 10: 76–94, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1007%2Fbf01940892">10.1007/bf01940892</a>, <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:20818200">20818200</a>.</li>
<li>Sedgewick, R. (2004), "19.8 Strong Components in Digraphs", Algorithms in Java, Part 5 – Graph Algorithms (3rd ed.), Cambridge MA: Addison-Wesley, pp. 205–216.</li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1">Sedgewick (2004). - Sedgewick, R. (2004), "19.8 Strong Components in Digraphs", Algorithms in Java, Part 5 – Graph Algorithms (3rd ed.), Cambridge MA: Addison-Wesley, pp. 205–216 <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">History of Path-based DFS for Strong Components, Harold N. Gabow, accessed 2012-04-24. <a href="http://www.cs.colorado.edu/~hal/Papers/DFS/pbDFShistory.html" target="_blank">http://www.cs.colorado.edu/~hal/Papers/DFS/pbDFShistory.html</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
</ol>

Path-based strong component algorithm open-in-new

Path-based strong component algorithm