A Bit of History
Arthur B. Kahn published this algorithm in 1962 in the paper "Topological sorting of large networks" in the Communications of the ACM — at a time when "large networks" meant something computers of the era could barely fit in memory. His motivation was resolving ordering problems in large-scale information systems: given a set of interdependent items (records, subroutines, tasks), produce a valid processing order in one clean pass, without the recursive call stack that a DFS-based approach requires. That practical, iterative, easy-to-implement-in-1962-hardware character is exactly why Kahn's algorithm remains the default choice in production dependency resolvers today, six decades later.
Working Principle
Kahn's algorithm reframes topological sorting as "repeatedly remove a vertex with no remaining unprocessed prerequisites": compute every vertex's in-degree, seed a queue with every vertex whose in-degree is already 0, and repeatedly dequeue a vertex, append it to the output, and decrement the in-degree of each of its neighbors — pushing any neighbor whose in-degree just hit 0.
from collections import deque, defaultdict
def kahns_pseudocode(vertices, edges):
"""
edges: list of (u, v) meaning u must come before v.
Returns a topological order, or None if a cycle exists.
"""
in_degree = {v: 0 for v in vertices}
adj = defaultdict(list)
for u, v in edges:
adj[u].append(v)
in_degree[v] += 1
queue = deque([v for v in vertices if in_degree[v] == 0])
order = []
while queue:
u = queue.popleft()
order.append(u)
for v in adj[u]:
in_degree[v] -= 1
if in_degree[v] == 0:
queue.append(v)
return order if len(order) == len(vertices) else None # None => cycle exists
Analogy: Clearing Prerequisites Off a Checklist
Imagine a checklist of tasks, each with prerequisites. You repeatedly scan for any task with zero remaining prerequisites, do it, and cross it off every other task's prerequisite list. Every time a task's prerequisite count hits zero, it becomes eligible. If you ever run out of eligible tasks while some remain on the list, those remaining tasks must be stuck in a circular dependency — exactly Kahn's built-in cycle check.
Worked Example
A tiny course-prerequisite DAG: Discrete Math → Data Structures → Algorithms; Discrete Math → Graph Theory → Algorithms.
flowchart LR
DM["Discrete Math (in=0)"] --> DS["Data Structures (in=1)"]
DM --> GT["Graph Theory (in=1)"]
DS --> ALG["Algorithms (in=2)"]
GT --> ALG
Initial queue: {Discrete Math} (only vertex with in-degree 0). Processing: dequeue Discrete Math, decrement Data Structures and Graph Theory to in-degree 0, enqueue both. Dequeue Data Structures, decrement Algorithms to in-degree 1 (not yet 0). Dequeue Graph Theory, decrement Algorithms to in-degree 0, enqueue it. Dequeue Algorithms. Final order: Discrete Math, Data Structures, Graph Theory, Algorithms — though "Discrete Math, Graph Theory, Data Structures, Algorithms" would have been equally valid, since Data Structures and Graph Theory don't depend on each other.
Kahn's vs. DFS-Based Topological Sort
Part 7 introduced the DFS-based approach (list vertices by decreasing finish time). Kahn's algorithm is a genuinely different strategy — BFS-flavored rather than recursion-flavored — but produces an equally valid (though not necessarily identical) topological order. Its main practical edge: cycle detection falls out naturally (the output is simply shorter than \(V\)) without needing DFS's white/gray/black vertex-coloring machinery, and it avoids recursion depth concerns entirely on very large or very "deep" DAGs.
Complexity Analysis
Computing in-degrees is \(O(V+E)\); each vertex is enqueued/dequeued exactly once, and each edge triggers exactly one in-degree decrement:
$$\text{Time: } O(V + E) \qquad \text{Space: } O(V)$$
Implementation
Real-World Applications
Package Managers and Build Systems
When npm, pip, or cargo resolve a dependency tree, they must install packages in an order where every package's dependencies are already installed — a topological sort of the dependency DAG. When a build system like GNU Make or Bazel decides which targets to compile first, it topologically sorts the file-dependency graph. In both cases, a detected cycle (package A depends on B which depends on A) is reported to the user as an unresolvable dependency conflict — precisely Kahn's algorithm's built-in cycle check surfacing as an error message.
Exercises
- Add a cyclic dependency to the worked example (e.g., make Algorithms a prerequisite of Discrete Math) and trace through Kahn's algorithm to confirm it correctly detects the cycle.
- Explain why using a priority queue instead of a plain queue for the "in-degree 0" frontier (breaking ties alphabetically, say) produces the lexicographically smallest valid topological order — a common requirement in deterministic build tooling.
- Modify the implementation to also report, when a cycle is detected, exactly which vertices are involved (hint: any vertex never appended to `order` is part of, or depends on, a cycle).
- Challenge: Implement the DFS-based topological sort from Part 7 and Kahn's algorithm side by side on the same DAG, and verify both produce valid (but possibly different) topological orders.
Limitations
Only Defined for DAGs, and Orders Are Rarely Unique
Kahn's algorithm (like any topological sort) is only meaningful on acyclic graphs — running it on a cyclic graph correctly reports failure but produces no partial ordering guarantee for the unprocessed vertices. And unless the DAG happens to be a simple path, a valid topological order is almost never unique — don't assume a specific order is "the" canonical one unless your tie-breaking rule (e.g., a priority queue, as in the exercises) is explicitly specified.