🧠 Mental Model
A topological order is a linear arrangement of a DAG's vertices such that every edge
u → v points "forward" (u before v). Kahn's builds it by repeatedly
peeling off vertices with no remaining prerequisites (in-degree 0). It's BFS with
in-degree bookkeeping.
Think dependency resolution: a task can run only once all its prerequisites are done. Kahn's runs
the ready tasks, which "unlocks" their dependents, and so on. If tasks remain but nothing is ready, you
have a circular dependency — a cycle.
⚙️ Mechanics
- Compute indegree[v] for all vertices.
- Enqueue every vertex with indegree = 0.
- Pop u, append to output; for each edge u → v, decrement
indegree[v]; if it hits 0, enqueue v.
- If the output has fewer than V vertices, the graph has a cycle (no valid order).
Invariant: a vertex is enqueued only after all its predecessors have already
been output. So the output order respects every edge.
📐 Correctness
Theorem
Kahn's algorithm outputs a valid topological order iff the graph is a DAG; otherwise it outputs
fewer than V vertices.
Proof
(Validity) When v is enqueued, indegree[v] has been
decremented to 0, meaning every predecessor u was already popped and output before
v. Thus for every edge u → v, u precedes
v — the defining property.
(Cycle ⇒ incomplete) Every vertex on a directed cycle has an in-edge from another
cycle vertex, so its in-degree never reaches 0 (each decrement requires a predecessor to be output
first, but they mutually block). Those vertices are never enqueued, so
|output| < V. Conversely, a DAG always has a source (in-degree 0) — else follow
in-edges backward forever in a finite graph, forcing a cycle — so the queue never empties early.
∎
📊 Complexity
| Metric | Value | Why |
|---|
| Time | O(V + E) | Each vertex enqueued once; each edge relaxes one in-degree. |
| Space | O(V) | In-degree array + queue. |
Kahn vs DFS topo (Day 12): Kahn's gives cycle detection "for free" via the count check and naturally yields lexicographically-smallest orders if you use a min-heap. DFS-based is terser and pairs with other DFS work.
💻 Reference Implementation (Java)
import java.util.*;
/** Kahn's topo sort. Returns order, or empty list if a cycle exists. */
public List<Integer> topoSort(int n, List<Integer>[] adj) {
int[] indeg = new int[n];
for (int u = 0; u < n; u++)
for (int v : adj[u]) indeg[v]++;
Queue<Integer> q = new ArrayDeque<>();
for (int v = 0; v < n; v++) if (indeg[v] == 0) q.offer(v);
List<Integer> order = new ArrayList<>();
while (!q.isEmpty()) {
int u = q.poll();
order.add(u);
for (int v : adj[u])
if (--indeg[v] == 0) q.offer(v); // v now unlocked
}
// fewer than n ⇒ cycle ⇒ no valid order
return order.size() == n ? order : new ArrayList<>();
}
// For lexicographically smallest order: use a PriorityQueue instead of ArrayDeque.
🎭 Problem Variances — how Big Tech disguises topological sort
Interviewers rarely say "topologically sort this." You detect it by the dependency /
ordering-with-prerequisites shape. Common disguises:
| Disguise / phrasing | What's really asked | Twist to handle |
|---|
| "Course schedule / prerequisites" | Is a valid order possible? (cycle check) | Return boolean vs the actual order |
| "Build/compile order," "task scheduling" | Produce one topo order | Ties → any order, or lexicographically smallest (min-heap) |
| "Alien dictionary / recover order" | Infer edges from adjacent items, then topo sort | Edge extraction is the hard part; watch invalid-prefix edge cases |
| "Unique reconstruction?" (seq. reconstruction) | Topo order that is unique | Queue must never hold >1 element at a time |
| "Parallel courses / min semesters" | Longest path in the DAG = # of Kahn layers | Process level-by-level (like BFS rings), count layers |
| "Minimum height trees" | Peel leaves inward (undirected topo-style) | Peel in-degree-1 nodes; stop at ≤2 centers |
| "Detect deadlock / eventual safe states" | Cycle membership | Reverse-graph Kahn, or DFS coloring (Day 12) |
Recognition heuristic: if items have "must come before" relationships and the graph is (or should be) acyclic, it's topological sort. If it must be unique, add the "queue size ≤ 1" check.
⚠️ Common Pitfalls
Forgetting the cycle check: if you don't compare order.size() to n, a cyclic graph silently returns a partial order.
Building the graph backwards: "a depends on b" means edge b → a. Getting direction wrong reverses everything.
Decrementing in-degree at the wrong time: only enqueue when it reaches exactly 0, not on every decrement.
🎯 Problems
LC 207
Course Schedule
Cycle-check variant — return whether a valid order exists.
Med
LC 210
Course Schedule II
Return the order itself; empty array if impossible.
Med
LC 1136
Parallel Courses
Layered Kahn — count BFS layers = minimum semesters (longest path).
Med
📚 References
- Kahn, A. B. (1962) — "Topological sorting of large networks," Comm. ACM 5(11), 558–562. The original algorithm.
- CLRS, 3rd ed., §22.4 — "Topological sort" (presents the DFS version; Kahn's is the BFS dual).
- cp-algorithms.com — "Topological Sorting" for both formulations.