Overview
Tarjan's algorithm tracks discovery indexes and low-link values to identify component roots during DFS.
SpecializedSource checked
Tarjan's Strongly Connected Components
Finds strongly connected components in one depth-first search pass.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Graph Traversal
- Difficulty
- Advanced
- Family
- Strong Components
- Tier
- Specialized
- Status
- Verified
- Review
- Source Checked
- Sources
- 3
- Formulas
- 0
- Relationships
- 5
- Code example
- Not ready
- Visualization
- Ready
- Aliases
- Tarjan SCC
Core Concepts
graph representationmutual reachabilitystack statetraversal orderstrong 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 Tarjan's Strongly Connected Components when you need to compute low-link values.
- Use it for directed graph 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 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
- Computes low-link values
- Pops completed components from a stack
Use Cases
- Directed graph analysis
- Cycle grouping
- Static analysis
Inputs
- Directed graph
Outputs
- Strongly connected component groups
Pseudocode
- 1.Run DFS with discovery indexes
- 2.Push each visited node on a stack
- 3.Update low-link values from neighbors
- 4.When a node is a component root, pop nodes to form a component
- 5.Continue until all nodes are visited
Canonical Example
- Input
- graph = {A: [B, C], B: [D], C: [], D: []}, start = A
- Output
- visited = [A, B, C, D]
- Explanation
- Tarjan's Strongly Connected Components: 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 with discovery indexes.
- Then preserve the next state change: Push each visited node on a stack.
- 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
- Low-link bookkeeping is compact but easy to implement incorrectly.
- 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 low-link values and a stack forming components.
Step 1 of 5: Run DFS with discovery indexes
low-link-stackNotes
Tarjan's Strongly Connected Components operates in O(V + E) time and O(V) space within the Strong Components family. Often compared with Kosaraju's Algorithm and Cycle Detection.
Sources (3)
What each reference supports for this entry.
Introduction to Algorithms (CLRS)
BookTextbook support for Tarjan's Strongly Connected Components's standard algorithm design, invariants, and complexity analysis.
Open sourceThe Algorithm Design Manual
BookAlgorithm catalog support for Tarjan's Strongly Connected Components's problem context, known alternatives, and practical selection tradeoffs.
Open sourceTarjan DFS Linear Graph Algorithms
PaperFoundational reference for Tarjan's linear-time strongly connected components algorithm.
Open sourceExplore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Relationships
View full relationship pageTarjan's SCC algorithm tracks low-link values during DFS.
Alternative toKosaraju's Algorithm
Both compute strongly connected components.
Related Algorithms
Tags
GraphStrongly Connected ComponentsStackTraversal