Computing Atlas

How Computing Was Built
Sign In
Text size
100%
Theme

Switch Atlas

Algorithm

Kosaraju's Algorithm

Graph Algorithm

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 Complexity
Theta(V+E) with an adjacency list; O(V^2) with an adjacency matrix. 2
Credited To
S. Rao Kosaraju, 1978 (unpublished); Micha Sharir, 1981 (independent publication). 2
Time Complexity
Time Complexity (category)
Linear Time -- O(n) 1
Connections

Credited To

Micha Sharir, Pioneers
Source Wikipedia: Kosaraju's Algorithm

In Field

Algorithms and Complexity Theory, Fields
Source Wikipedia: Kosaraju's Algorithm

Invented By

Micha Sharir, Pioneers
Source Wikipedia: Kosaraju's Algorithm

Uses Design Technique

Recursion, Concepts
Source Wikipedia: Kosaraju's Algorithm
Sources
1. Kosaraju's Algorithm (Wikipedia)
Wikipedia infobox: time complexity linear
Quote, Wikipedia infobox: time complexity linear
linear
View the Source
2. Wikipedia: Kosaraju's Algorithm
Wikimedia Foundation
  • Lead 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.
  • Complexity
    If the graph is represented as an adjacency matrix, the algorithm requires Ο(V2) time.
  • Lead section
    Rao Kosaraju and Micha Sharir. Kosaraju suggested it in 1978 but did not publish it, while Sharir independently discovered it and published it in 1981.
  • Uses Design Technique: Recursion, Article body
    For each vertex u of the graph do Visit(u), where Visit(u) is the recursive subroutine: If u is unvisited then: Mark u as visited.
  • In Field: Algorithms and Complexity Theory, Lead sentence
    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.
  • Credited To: Micha Sharir, Lead
    Aho, Hopcroft and Ullman credit it to S. Rao Kosaraju and Micha Sharir.
View the Source
Wikidata: Kosaraju's Algorithm
Wikidata Q2655281, class allow-list match (w-wdresolver-0926)View the Source
Comments (0)
No comments yet. Be the first to share a thought.
Reader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.