Content deleted Content added
Citation bot (talk | contribs) Alter: template type, title. Add: isbn, series. | Use this bot. Report bugs. | Suggested by Neko-chan | #UCB_webform 150/500 |
Undid revision 1230141503 by Citation bot (talk) and fix the reference properly rather than borking it more than it was already borked, as the bot insists on doing |
||
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.
In Tarjan's paper, when <code>''w''</code> is on the stack, <code>''v''.lowlink</code> is updated with the assignment <code>''v''.lowlink := min(''v''.lowlink, ''w''.index)</code>.<ref name=Tarjan/>{{rp|157}} A common variation is to instead use <code>''v''.lowlink := min(''v''.lowlink, ''w''.lowlink)</code>.<ref>{{cite
| last1 = Kordy | first1 = Piotr
| last2 = Langerak | first2 = Rom
| last3 = Mauw | first3 = Sjouke
| last4 = Polderman | first4 = Jan Willem
| editor1-last = Jones | editor1-first = Cliff B.
| editor2-last = Pihlajasaari | editor2-first = Pekka
| editor3-last = Sun | editor3-first = Jun
| contribution = A symbolic algorithm for the analysis of robust timed automata
| contribution-url = https://satoss.uni.lu/members/sjouke/papers/KLMP14.pdf
| doi = 10.1007/978-3-319-06410-9_25
| isbn = 978-3-319-06409-3
| pages = 351–366
| publisher = Springer
| series = Lecture Notes in Computer Science
| title = FM 2014: Formal Methods – 19th International Symposium, Singapore, May 12–16, 2014. Proceedings
| volume = 8442
| year = 2014}}</ref><ref>{{cite web |title=Lecture 19: Tarjan’s Algorithm for Identifying Strongly Connected Components in the Dependency Graph |url=http://courses.cms.caltech.edu/cs130/lectures/CS130-Wi2024-Lec19.pdf |website=CS130 Software Engineering |publisher=Caltech |date=Winter 2024}}</ref> This modified algorithm does not compute the lowlink numbers as Tarjan defined them, but the test <code>''v''.lowlink = ''v''.index</code> still identifies root nodes of strongly connected components, and therefore the overall algorithm remains valid.<ref name="CMU2018">{{cite web |title=Lecture #19: Depth First Search and Strong Components |url=https://www.cs.cmu.edu/~15451-f18/lectures/lec19-DFS-strong-components.pdf |website=15-451/651: Design & Analysis of Algorithms |publisher=Carnegie Mellon |date=1 November 2018}}</ref>
== Complexity ==
| |||