Topological sort
When some tasks must come before others, a topological sort finds an order that respects every rule, or proves that none exists because the rules go in a circle.
A topological order puts every link's start before its end
Courses with prerequisites, build steps that need other steps' output, spreadsheet cells that read other cells: each is a directed graph where a link u → v means "u before v". A topological order lists the nodes so that every link points forward: each node comes after everything that leads to it. Finding one is called a topological sort.
Such an order exists exactly when the graph has no cycle. If a → b → c → a, none of the three can go first. A directed graph with no cycle is a directed acyclic graph, or DAG, and every DAG has at least one topological order, often many.
The rule
A directed graph has a topological order if and only if it has no cycle. Repeatedly take a node with nothing left pointing into it; if you get stuck before every node is taken, the rest contains a cycle.
Kahn's algorithm takes whatever has no prerequisites left
Kahn's algorithm builds the order with in-degrees. Every node with in-degree 0 has no prerequisites, so it can go first: put those in a queue. Each time you take a node, its links are satisfied, so lower the in-degree of each node it points to. A node whose count reaches 0 joins the queue.
Course 3 waited for both 1 and 2. If several courses are ready at once, any of them may go next, which is why a DAG can have many valid orders.
A cycle shows up as a link back into the current route
Kahn's algorithm notices a cycle at the end: the order comes out shorter than n, because the nodes on a cycle never reach in-degree 0. DFS finds the cycle itself. Keep the nodes on the current route of the search; a link to one of them leads back into the route, and that is a cycle.
A node that was finished earlier is different: everything after it has been explored and was fine, so a second link into it is harmless. That is why the search keeps two records, the current route and the finished nodes.
Without a cycle, the order in which nodes finish, reversed, is a topological order: a node only finishes after everything it points to. That is the DFS way to sort, an alternative to Kahn's algorithm.
Work through the order, and each node's answer is ready when you reach it
A topological order is the right order for any calculation where a node depends on the nodes pointing into it. When you take a node, all of its inputs are final. Here each course ends at the latest end among its prerequisites plus its own duration, and courses can run side by side.
The answer, 12, comes from the chain 0 → 2 → 4 → 5, even though course 2 is the shortest: the slowest chain decides. This is dynamic programming over a DAG, and the same pass finds the longest route, counts routes or adds up values along them.
Kahn's algorithm or DFS: both O(n + m)
Kahn's algorithm | DFS | |
|---|---|---|
Idea | Take nodes with in-degree 0, lower their neighbors' counts | Finish order, reversed |
Uses | In-degrees and a queue | Recursion or a stack, a current route and a finished set |
Spots a cycle | Fewer than n nodes come out | A link back into the current route |
Good for | Layers (everything ready at the same time), dependency passes | Finding the cycle itself, graphs already searched by DFS |
3 questions
Remember this
- A topological order puts every link's start before its end; it exists exactly when the directed graph has no cycle.
- Kahn's algorithm repeatedly takes a node with in-degree 0 and lowers its neighbors' counts: O(n + m).
- DFS spots a cycle as a link back into the current route; reversed finish order is a topological order.
- Processing nodes in topological order makes every node's inputs final when you reach it.
Now solve some yourself
Only this topic 0 of 10 solved
- MediumEvery ancestor of each node in a DAG
- MediumAn order to take the courses in
- MediumAn alphabet that puts the names in order
- MediumNodes that can't lead into a cycle
- MediumThe quietest richer-or-equal person
- MediumIs one course a prerequisite of another?
- MediumCenters of a tree, by trimming the leaves
- HardFill a matrix that respects row and column orders
- HardOrder items that also belong to groups
- HardLongest cycle when each node has one link out
Mixed with topics you have practiced 0 unlocked
4 more once you have practiced Hash tables & maps, Dynamic programming: basics, Grid traversal. Play one of its examples to the end and solve one of its problems to unlock them.
Problems open on their own sites (LeetCode, Codeforces, CodeChef, AtCoder, CSES) in a new tab. Tick Solved when you get it accepted there; your ticks decide which mixed problems open next.
Next