Overview
Kahn's algorithm tracks indegrees in a directed graph and emits nodes whose prerequisites have all been removed, making cycles visible when nodes remain unprocessed.
CoreSource checked
Kahn's Algorithm
Produces a topological ordering by repeatedly removing nodes with no incoming edges.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Graph Traversal
- Difficulty
- Intermediate
- Family
- Topological Ordering
- Tier
- Core
- Status
- Verified
- Review
- Source Checked
- Sources
- 2
- Formulas
- 1
- Relationships
- 3
- Code example
- Ready
- Visualization
- Ready
Core Concepts
indegree countingqueue frontierdirected acyclic graphtopological order
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 when analyzing graph structure needs indegree counting.
- Use when the input matches the assumptions behind topological Ordering.
When Not to Use
- Avoid when the graph is so large that it needs streaming or external-memory handling.
- Avoid when a simpler algorithm gives the required result with less setup.
What It Does
- Produces a topological ordering by repeatedly removing nodes with no incoming edges
- Uses indegree counting and queue frontier to guide the work.
- Produces visited nodes.
Use Cases
- Analyzing graph structure
- Finding connectivity patterns
- Preparing graph-derived orderings
Inputs
- Graph
- Start nodes or query nodes
- Traversal state
Outputs
- Visited nodes
- Derived graph relationships
Key Formulas (1)
Indegree decrement
indegree[v] = indegree[v] − 1
in_degree[v] = in_degree[v] - 1Updates a neighbor after one incoming prerequisite edge is removed.
Pseudocode
- 1.Prepare the inputs and state needed for Kahn's Algorithm.
- 2.Apply the indegree counting step while the stopping condition has not been met.
- 3.Update intermediate state and discard invalid candidates.
- 4.Return visited nodes.
Canonical Example
- Input
- Kahn's Algorithm with a minimal inspectable input
- Output
- Visited nodes
- Explanation
- Kahn's Algorithm applies indegree counting to produce visited nodes.
Implementation Notes
- Keep visitation state and edge classification state separate.
- Keep the indegree counting step separate enough to test independently.
Common Pitfalls
- Mixing directed and undirected edge assumptions can produce incorrect graph relationships.
- Forgetting to check edge cases can make Kahn's Algorithm look correct on only ideal inputs.
Interactive Mechanism Walkthrough
Graph Frontier & Edge RelaxationHighlight active nodes, discovered edges, and the graph structure produced by each step.
Step 1 of 4: Prepare the inputs and state needed for Kahn's Algorithm.
graph-traversal-mechanismNotes
Kahn's Algorithm should be used with the assumptions and tradeoffs of topological Ordering in mind.
Sources (2)
What each reference supports for this entry.
Introduction to Algorithms (CLRS)
BookTextbook support for Kahn's Algorithm's standard algorithm design, invariants, and complexity analysis.
Open sourceThe Algorithm Design Manual
BookAlgorithm catalog support for Kahn'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 pageDepends onDirected Acyclic Graph
Kahn's Algorithm expects the graph to be acyclic for a complete ordering.
Variant ofTopological Sort
Kahn's Algorithm computes a topological order by repeatedly removing zero-indegree vertices.
Related Algorithms
Tags
GraphDirected Acyclic GraphTopological OrderQueue