Topological sort
In what order can dependent tasks run?
Forty migrations, 820 attempts
A ledger service ships with 40 database migrations, and each one declares what it needs: a table, a column, another migration. The deploy tool ignores all of that and runs them in file-name order. In one release, 017_add_settlement_index runs before 023_create_settlements, and the deploy fails.
The quick fix is a loop: try every migration that has not succeeded yet, and repeat until all have succeeded. It works. Now time it on a staging copy where the dependencies form one long chain that runs against the file order, so that each pass gets exactly one migration through. Count the attempts. Pass one makes 40 attempts, pass two makes 39, and so on down to 1: 40 passes and 820 attempts. At three seconds an attempt, the deploy takes 41 minutes. Worse, two migrations merged last week each need the other. On those, the loop never ends.
Every failed attempt was a migration tried before the migrations it needs had run. So instead of trying and retrying, ask before each run which migration is certain to succeed.
Pause and predict Which migration can safely run first, with no retries?
Place only what waits on nothing
Tasks depend on other tasks. Draw an arrow from each task to the tasks that need it. A topological order lists the tasks so that every arrow points forward: nothing is placed before something it needs.
Which task can go first? One with no arrow pointing into it. The number of arrows pointing into a node is its indegree, so this task has indegree 0. Place it, delete the arrows that leave it, and you are left with the same question on a smaller graph. That is Kahn's algorithm.
A node with count 0 is always safe to place next, because everything it needs is already placed, so putting it next breaks no arrow. Placing it also only lowers other nodes' counts, so it can never make another node harder to place. So whichever ready node you take, it is never a wrong move, and there is no need to search or undo.
That freedom also means there are usually many valid orders. When two nodes sit in the queue together, either can go first. A problem that asks for "an order" accepts any of them.
When the queue empties too early
Pause and predict The queue is empty, and 3 of the nodes were never placed. What does that prove?
Each node enters the queue once and each edge is removed once, so the cost is O(V + E).
The arrow points from the prerequisite
Pause and predict Course problems give pairs [a, b] meaning "b before a". For [1, 0], which way does the arrow go?
The other way: three colours
Pause and predict The graph is a diamond, with edges 0 to 1, 0 to 2, 1 to 3 and 2 to 3. A DFS that keeps one visited flag per node reaches 3 a second time, through 2. Is that a cycle?
A node turns black only after every node it can reach has turned black. So if you list the nodes in the order they turn black and read the list newest first, you also get a topological order. Both methods are O(V + E). Kahn's algorithm needs no recursion, which matters on a chain of 2,000 nodes.
A neural network's backward pass leans on the same fact. Autograd records the operations in the order they ran, which is a topological order, and walks that record backwards from the loss, so every node's gradient is complete before it is passed on.
How to recognise it
When a phrase like these appears, check that the edges are directed. "Before" only means something when the relation has a direction.
Pause and predict Roads connect cities in both directions, and the question is whether the roads contain a loop. Is this a topological sort problem?
Three that only look like it
- When the question is about reachability or distance, with no rule about order, use plain BFS or DFS, from the graphs unit.
- When groups merge, or you need a cycle in an undirected graph, use union-find. A DAG depends on the direction of its edges, and union-find ignores direction.
- When you need the cheapest route by weight, use shortest paths. On a DAG a topological order can be the first step, but the order alone does not give the answer.
Where it bites
Pause and predict A cycle stops Kahn's queue after 4 of 6 courses are placed. What should findOrder return?
- Reversed edges. The pair
[a, b]means b comes first, so the arrow goes from b to a and a's count goes up. Course Schedule cannot detect the mistake, but Course Schedule II returns the order backwards. - Using one visited flag for cycle detection. With a single flag, a diamond looks like a cycle. The search needs separate states for "on the current path" (grey) and "finished" (black).
- Starting only with nodes that appear in an edge. A node with no rules at all still needs a place in the order.
- Expecting one particular order. Any order that respects every edge is right. If a particular one is required, the problem says which, for example the smallest, which you get with a min-heap in place of the queue.