Editing Strongly connected component (section)

===DFS-based linear-time algorithms===
Several [[algorithm]]s based on [[depth-first search]] compute strongly connected components in linear time.
*[[Kosaraju's algorithm]] uses two passes of depth-first search. The first, in the original graph, is used to choose the order in which the outer loop of the second depth-first search tests vertices for having been visited already and [[recursion|recursively]] explores them if not. The second depth-first search is on the [[transpose graph]] of the original graph, and each recursive exploration finds a single new strongly connected component.<ref>[[Thomas H. Cormen]], [[Charles E. Leiserson]], [[Ronald L. Rivest]], and [[Clifford Stein]]. ''[[Introduction to Algorithms]]'', Second Edition. MIT Press and McGraw-Hill, 2001. {{isbn|0-262-03293-7}}. Section 22.5, pp.&nbsp;552&ndash;557.</ref><ref name="hong2013fast" /> It is named after [[S. Rao Kosaraju]], who described it (but did not publish his results) in 1978; [[Micha Sharir]] later published it in 1981.<ref>{{citation|doi=10.1016/0898-1221(81)90008-0|title=A strong-connectivity algorithm and its applications in data flow analysis|year=1981|last1=Sharir|first1=Micha|author-link1=Micha Sharir|journal=Computers & Mathematics with Applications|volume=7|pages=67–72|doi-access=free}}</ref>
*[[Tarjan's strongly connected components algorithm]], published by [[Robert Tarjan]] in 1972,<ref>{{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|s2cid=16467262 }}</ref> performs a single pass of depth-first search. It maintains a [[Stack (abstract data type)|stack]] of vertices that have been explored by the search but not yet assigned to a component, and calculates "low numbers" of each vertex (an index number of the highest ancestor reachable in one step from a descendant of the vertex) which it uses to determine when a set of vertices should be popped off the stack into a new component.
*The [[path-based strong component algorithm]] uses a depth-first search, like Tarjan's algorithm, but with two stacks. One of the stacks is used to keep track of the vertices not yet assigned to components, while the other keeps track of the current path in the depth-first search tree. The first linear time version of this algorithm was published by [[Edsger W. Dijkstra]] in 1976.<ref>{{citation
 | last = Dijkstra | first = Edsger | author-link = Edsger Dijkstra
 | location = NJ
 | at = Ch.&nbsp;25
 | publisher = Prentice Hall
 | title = A Discipline of Programming
 | year = 1976}}.</ref>
Although Kosaraju's algorithm is conceptually simple, Tarjan's and the path-based algorithm require only one depth-first search rather than two.