Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Tarjan's strongly connected components algorithm
open-in-new
<p>Tarjan's strongly connected components algorithm is an <a href="/facts/Algorithm/fnl5NmRt">algorithm</a> in <a href="/facts/Graph_theory/VVPCd4TX">graph theory</a> for finding the <a href="/facts/Strongly_connected_component/P6rBqb7W">strongly connected components</a> (SCCs) of a <a href="/facts/Directed_graph/YBdfQ0um">directed graph</a>. It runs in <a href="/facts/Linear_time/77T62gmf">linear time</a>, matching the time bound for alternative methods including <a href="/facts/Kosaraju%2527s_algorithm/MYLcDEc0">Kosaraju's algorithm</a> and the <a href="/facts/Path-based_strong_component_algorithm/PctG4xP4">path-based strong component algorithm</a>. The algorithm is named for its inventor, <a href="/facts/Robert_Tarjan/kn1pMCN0">Robert Tarjan</a>. </p>