Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Path-based strong component algorithm
open-in-new
<p>In <a href="/facts/Graph_theory/VVPCd4TX">graph theory</a>, the <a href="/facts/Strongly_connected_component/P6rBqb7W">strongly connected components</a> of a <a href="/facts/Directed_graph/YBdfQ0um">directed graph</a> may be found using an algorithm that uses <a href="/facts/Depth-first_search/luxJKVph">depth-first search</a> in combination with two <a href="/facts/Stack_(data_structure)/bj7l94v1">stacks</a>, one to keep track of the vertices in the current component and the second to keep track of the current search path. Versions of this algorithm have been proposed by Purdom (1970), Munro (1971), Dijkstra (1976), Cheriyan & Mehlhorn (1996), and Gabow (2000); of these, Dijkstra's version was the first to achieve <a href="/facts/Linear_time/77T62gmf">linear time</a>. </p>