Topological Sort
01 / The one-sentence essence
Linearize a directed acyclic graph so every edge points left-to-right in the output — each node enters the order only after every node that points to it has already left.
Problemtopological order of a DAGNodes4Edges4
Count in-degrees. Any node with no incoming edges is a source — ready to process first.
step
0 / 13
queue
[—]
action
init
result
[—]
0 / 13
02 / The pattern signature
# Kahn's algorithm — drain in-degrees from a queue of sourcesin_degree ← count incoming edges per nodequeue ← nodes with in_degree[node] == 0result ← []while queue not empty:u ← queue.pop_front()result.append(u)for v in adj[u]:in_degree[v] -= 1if in_degree[v] == 0: queue.append(v)if len(result) < n: # cycle detectedreturn []return result
03 / When to recognize this pattern
"prerequisites" / "depends on"
Course scheduling, task ordering, build systems, package managers, formula spreadsheets. Anything with a dependency graph needs topological order.
"can we even do this in some order?"
The same algorithm detects whether any valid order exists. If Kahn's queue empties early, the unprocessed nodes form a cycle — the answer is no. LC 207 is exactly this question.
"DAG"
The problem statement explicitly mentions a directed acyclic graph. Whenever you see "DAG," topological sort is the spinal cord that everything else hangs off of — longest path in a DAG, shortest path in a DAG, count paths in a DAG.
"BFS feels right but order matters"
When a plain BFS would explore neighbors arbitrarily but the problem demands respect for dependencies, you're really running Kahn's on the dependency DAG.
04 / Common pitfalls
i.
Mixing up edge direction.
(a, b) in the input might mean "a is a prerequisite of b" (a → b) or "a depends on b" (b → a). Read the problem statement carefully — the algorithm is correct in both cases, but only one matches the intended ordering. LC 210 uses [a, b] = "to take a, you must take b first," which is the reverse of typical edge notation.ii.
Confusing "no cycle" with "valid order exists."
These are the same condition for a DAG, but the failure mode is different in code. Detect cycles by checking
len(result) == n at the end, not by trying to find them up-front. Kahn's naturally rejects cyclic input.iii.
Assuming the order is unique.
Most DAGs have many valid topological orders. If the problem asks for "the lexicographically smallest order" (LC 269), swap the queue for a min-heap — the rest of Kahn's stays the same.
05 / Go practice — on LeetCode
Four problems across the family. The first two are the textbook cycle-detection / order-output pair. The third lifts the algorithm into derivation (figure out the alphabet from word ordering); the fourth introduces parallel-execution slack.