Content deleted Content added
Aalok.sathe (talk | contribs) m →External links: reworded to make sense in context |
→The algorithm in pseudocode: it could be implemented as an array but really it's a stack |
||
Line 36:
''index'' := 0
''S'' := empty
'''for each''' ''v'' '''in''' ''V'' '''do'''
'''if''' (''v''.index is undefined) '''then'''
Line 84:
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 <tt>''v''.lowlink := min(''v''.lowlink, ''w''.index) </tt> is the correct way to update ''v.lowlink'' if ''w'' is on stack. Because ''w'' is on the stack already, ''(v, w)'' is a back-edge in the DFS tree and therefore ''w'' is not in the subtree of ''v''. Because ''v.lowlink'' takes into account nodes reachable only through the nodes in the subtree of ''v'' we must stop at ''w'' and use ''w.index'' instead of ''w.lowlink''.
== Complexity ==
| |||