Content deleted Content added
m grammar/usage - 'return back'->return, typo(s) fixed: In other words → In other words,, replaced: accessdate → access-date |
update usages of "Tarjan's algorithm" to the unambiguous "Tarjan's SCC algorithm" |
||
Line 2:
|class=
|image= [[File:Tarjan's Algorithm Animation.gif|250px]]
|caption = Tarjan's algorithm
|data=[[Graph (data structure)|Graph]]
|time= <math>O(|V|+|E|)</math>
Line 11:
|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]].
== Overview ==
Line 97:
While there is nothing special about the order of the nodes within each strongly connected component, one useful property of the algorithm is that no strongly connected component will be identified before any of its successors. Therefore, the order in which the strongly connected components are identified constitutes a reverse [[Topological sorting|topological sort]] of the [[Directed acyclic graph|DAG]] formed by the strongly connected components.<ref>{{cite web|last=Harrison|first=Paul|title=Robust topological sorting and Tarjan's algorithm in Python|url=http://www.logarithmic.net/pfh/blog/01208083168|access-date=9 February 2011}}</ref>
[[Donald Knuth]] described Tarjan's SCC algorithm as one of his favorite implementations in the book ''The Stanford GraphBase''.<ref>Knuth, ''The Stanford GraphBase'', pages 512–519.</ref>
He also wrote:<ref>{{cite book|last=Knuth|first=Donald|title=Twenty Questions for Donald Knuth|url=http://www.informit.com/articles/article.aspx?p=2213858&WT.mc_id=Author_Knuth_20Questions|date=2014-05-20}}</ref> {{quote|The data structures that he devised for this problem fit together in an amazingly beautiful way, so that the quantities you need to look at while exploring a directed graph are always magically at your fingertips. And his algorithm also does topological sorting as a byproduct.}}
| |||