Content deleted Content added
→The algorithm in pseudocode: remove overly dogmatic stmt. The original algorithm does use w.index, not w.lowlink; that is not an argument why it is necessary to do it that way. |
different note, the lecture notes are unfortunately the best sources I could find, seems nobody published a paper about it or mentioned it in a book |
||
Line 12:
|complete=
}}
'''Tarjan's strongly connected components algorithm''' is an [[algorithm]] in [[graph theory]] for finding the [[strongly connected component]]s (SCCs) of a [[directed graph]]. It runs in [[linear time]], matching the time bound for alternative methods including [[Kosaraju's algorithm]] and the [[path-based strong component algorithm]]. The algorithm is named for its inventor, [[Robert Tarjan]].<ref name=Tarjan>{{citation|first=R. E.|last=Tarjan|author-link=Robert Tarjan|title=Depth-first search and linear graph algorithms|journal=[[SIAM Journal on Computing]]|volume=1|year=1972|issue=2|pages=146–160|doi=10.1137/0201010|citeseerx=10.1.1.327.8418|url=https://web.archive.org/web/20170829214726id_/http://www.cs.ucsb.edu/~gilbert/cs240a/old/cs240aSpr2011/slides/TarjanDFS.pdf}}</ref>
== Overview ==
Line 61:
''// Successor w is in stack S and hence in the current SCC''
''// If ''w'' is not on stack, then (''v'', ''w'') is an edge pointing to an SCC already found and must be ignored
''//
''v''.lowlink := min(''v''.lowlink, ''w''.index)
Line 80 ⟶ 79:
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 journal |last1=Kordy |first1=Piotr |last2=Langerak |first2=Rom |last3=Mauw |first3=Sjouke |last4=Polderman |first4=Jan Willem |title=A Symbolic Algorithm for the Analysis of Robust Timed Automata |journal=FM 2014: Formal Methods |date=2014 |volume=8442 |pages=351–366 |doi=10.1007/978-3-319-06410-9_25 |url=https://satoss.uni.lu/members/sjouke/papers/KLMP14.pdf}}</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>{{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 ==
| |||