Tarjan's strongly connected components algorithm finds the strongly connected components of a directed graph, the maximal sets of vertices each reachable from every other vertex in the same set, in a single depth-first traversal. It runs in linear time, matching the time bound of alternative methods such as Kosaraju's algorithm, and is named for its inventor, Robert Tarjan, who published it in 1972 in Depth-first search and linear graph algorithms. This description is adapted from Wikipedia contributors under CC BY-SA 4.0; changes were made. https://creativecommons.org/licenses/by-sa/4.0/
Facts
Time ComplexityO(V+E), linear in the number of vertices and edges. 1 Credited ToRobert Tarjan, 1972 (Depth-first search and linear graph algorithms, SIAM Journal on Computing, volume 1, issue 2). 1 Connections
Invented By
Robert Tarjan published his linear-time algorithm for finding strongly connected components of a directed graph in 1972, based on depth-first search.
Source Wikipedia: Robert Tarjan
Sources
1. Wikipedia: Tarjan's Strongly Connected Components Algorithm
Wikimedia FoundationLead section
Tarjan's strongly connected components algorithm is an algorithm in graph theory for finding the strongly connected components (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. The algorithm is named for its inventor, Robert Tarjan.
Body, complexity discussion
linear in the number of edges and nodes in G
Body, references
his original work was published in 1972 in a paper titled Depth-first search and linear graph algorithms in the SIAM Journal on Computing, volume 1, issue 2, pages 146-160
View the Source Reader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.