Revision as of 19:58, 12 October 2024 edit JJMC89 bot III (talk \| contribs) Bots, Administrators 4,309,158 edits m Moving Category:Algorithms in graph theory to Category:Graph algorithms per Wikipedia:Categories for discussion/Log/2024 October 4 Tag: Manual revert ← Previous edit		Revision as of 18:30, 21 January 2025 edit undo 131.215.220.162 (talk) Correct link for Caltech CS130 Winter 2024 lecture Next edit →
Line 98: \| 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-2024wi/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 ==

Tarjan's strongly connected components algorithm: Difference between revisions