Many things come with "this before that" rules: courses and their prerequisites, build steps, spreadsheet cells that depend on other cells. Draw each rule as an arrow X → Y ("X must come before Y") and you get a directed graph. A topological order lists every node so that all arrows point forward.
That's only possible if the graph has no cycle: if A must precede B, B precede C, and C precede A, nothing can go first. A directed graph without cycles is called a DAG (directed acyclic graph).
If at some point nodes remain but none is ready, they are all waiting on each other: the graph has a cycle, and no topological order exists. So Kahn's algorithm also detects cycles.
Under each node not yet placed is its current in-degree (in=…). Placed nodes are filled, and the arrows they used up fade. When several nodes are ready at once, any of them is a valid choice; these pages always take the alphabetically first, so each question has one answer.
| Kahn's algorithm | |
|---|---|
| Time | O(V + E): each node is placed once and each arrow removed once. |
| Alternative | Run DFS and list nodes in reverse order of when they finish. |