Overview
Kosaraju's Algorithm orders nodes by finish time, reverses the graph, and then collects strongly connected components.
SpecializedSource checked
Kosaraju's Algorithm
Finds strongly connected components using two passes of depth-first search.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Graph Traversal
- Difficulty
- Intermediate
- Family
- Strong Components
- Tier
- Specialized
- Status
- Verified
- Review
- Source Checked
- Sources
- 2
- Formulas
- 0
- Relationships
- 4
- Code example
- Ready
- Visualization
- Ready
- Aliases
- Kosaraju-Sharir Algorithm
Core Concepts
graph representationmutual reachabilitytraversal orderrecursive decompositionstrong componentsvisited setfrontier expansion
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(V + E)
Average
O(V + E)
Worst
O(V + E)
Space
O(V)
When to Use
- Use Kosaraju's Algorithm when you need to order nodes by DFS finish time.
- Use it for dependency analysis with inputs like directed graph.
- Use it when relationships are naturally modeled as nodes connected by edges.
- Use it when the Strong Components tradeoff is acceptable for the problem size.
When Not to Use
- Avoid it when recursion depth can exceed the runtime stack limit.
- Avoid it when the graph is so large that storing every visited node is not practical.
- Avoid it when the required output is not strongly connected component groups.
What It Does
- Orders nodes by DFS finish time
- Groups mutually reachable nodes in a directed graph
Use Cases
- Dependency analysis
- Compiler optimization
- Directed network structure
Inputs
- Directed graph
Outputs
- Strongly connected component groups
Pseudocode
- 1.Run DFS and record finish order
- 2.Reverse every graph edge
- 3.Process nodes in reverse finish order
- 4.Run DFS on the reversed graph
- 5.Each DFS tree is one component
Canonical Example
- Input
- graph = {A: [B, C], B: [D], C: [], D: []}, start = A
- Output
- visited = [A, B, C, D]
- Explanation
- Kosaraju's Algorithm: The traversal starts at A and visits reachable nodes by following edges.
Implementation Notes
- Keep the input contract explicit: Directed graph.
- Use this step as the implementation spine: Run DFS and record finish order.
- Then preserve the next state change: Reverse every graph edge.
- Keep node ids, edge direction, and visited state explicit in the implementation.
- Represent neighbors consistently and keep traversal state separate from the graph data.
Common Pitfalls
- The algorithm is simple but requires access to the reversed graph.
- Not defining directed versus undirected edges clearly can change the result.
- Forgetting to mark visited nodes before revisiting cycles or shared neighbors.
- Returning strongly connected component groups without handling empty, invalid, or boundary inputs.
Interactive Mechanism Walkthrough
Graph Frontier & Edge RelaxationShow finish order from the first pass and component discovery in the reversed graph.
Step 1 of 5: Run DFS and record finish order
component-passNotes
Kosaraju's Algorithm operates in O(V + E) time and O(V) space within the Strong Components family. Often compared with Tarjan's Strongly Connected Components and Depth-First Search.
Sources (2)
What each reference supports for this entry.
Introduction to Algorithms (CLRS)
BookTextbook support for Kosaraju's Algorithm's standard algorithm design, invariants, and complexity analysis.
Open sourceThe Algorithm Design Manual
BookAlgorithm catalog support for Kosaraju's Algorithm's problem context, known alternatives, and practical selection tradeoffs.
Open sourceExplore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Relationships
View full relationship pageKosaraju's Algorithm uses DFS passes on the graph and its transpose.
Alternative toTarjan's Strongly Connected Components
Both compute strongly connected components.
Related Algorithms
Tags
GraphStrongly Connected ComponentsTraversalRecursion