Tarjan's strongly connected components algorithm: Difference between revisions

Revision as of 01:54, 17 June 2018

Revision as of 04:48, 17 June 2018

Line 13:

'''Tarjan's algorithm''' is an [[algorithm]] in [[graph theory]] for finding the [[strongly connected component]]s of a [[Graph (data structure)|graph]]. It runs in [[linear time]], matching the time bound for alternative methods including [[Kosaraju's algorithm]] and the [[path-based strong component algorithm]]. Tarjan's algorithm is named for its inventor, [[Robert Tarjan]].<ref>{{citation|first=R. E.|last=Tarjan|authorlink=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}}</ref>

<ref></ref>== Overview ==

The algorithm takes a [[directed graph]] as input, and produces a [[Partition of a set|partition]] of the graph's [[Vertex (graph theory)|vertices]] into the graph's strongly connected components. Each vertex of the graph appears in exactly one of the strongly connected components. Any vertex that is not on a directed cycle forms a strongly connected component all by itself: for example, a vertex whose in-degree or out-degree is 0, or any vertex of an acyclic graph.