Kosaraju's algorithm, also called Kosaraju-Sharir's algorithm, finds the strongly connected components of a directed graph in linear time by performing two depth-first searches, one on the graph and one on its transpose. S. Rao Kosaraju suggested the algorithm in 1978 but did not publish it; Micha Sharir independently discovered and published it in 1981. 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 ComplexityTheta(V+E) with an adjacency list; O(V^2) with an adjacency matrix. 1 Credited ToS. Rao Kosaraju, 1978 (unpublished); Micha Sharir, 1981 (independent publication). 1 Sources
1. Wikipedia: Kosaraju's Algorithm
Wikimedia FoundationLead section
In computer science, Kosaraju-Sharir's algorithm (also known as Kosaraju's algorithm) is a linear time algorithm to find the strongly connected components of a directed graph.
Body, complexity discussion
The algorithm runs in Theta(V+E) (linear) time with an adjacency list representation. With an adjacency matrix, it requires O(V^2) time.
Body, history
S. Rao Kosaraju suggested the algorithm in 1978 but did not publish it. Micha Sharir independently discovered and published it in 1981.
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.