Content deleted Content added
→The algorithm in pseudocode: some more on using lowlink vs index, couldn't find any reliable source with a proof that it worked so wrote some vague FUD Tag: Reverted |
Undid revision 1141010662 by Mathnerd314159 (talk) If you have to resort to unsourced editorializations like that to explain away the difference, then it's not ready to include in the article |
||
Line 80:
When each node finishes recursing, if its lowlink is still set to its index, then it is the root node of a strongly connected component, formed by all of the nodes above it on the stack. The algorithm pops the stack up to and including the current node, and presents all of these nodes as a strongly connected component.
Note that <code>''v''.lowlink := min(''v''.lowlink, ''w''.index)</code> is the correct way to update <code>''v.lowlink''</code> if <code>''w''</code> is on stack. Because <code>''w''</code> is on the stack already, <code>''(v, w)''</code> is a back-edge in the DFS tree and therefore <code>''w''</code> is not in the subtree of <code>''v''</code>. Because <code>''v.lowlink''</code> takes into account nodes reachable only through the nodes in the subtree of <code>''v''</code> we must stop at <code>''w''</code> and use <code>''w.index''</code> instead of <code>''w.lowlink''</code>
== Complexity ==
| |||