Topological Sort
A directed acyclic graph is a set of tasks with prerequisites, and a topological order is a schedule that respects them. Kahn's algorithm keeps taking a task with no unfinished prerequisites. Depth-first search finishes a task only after everything downstream of it, so its finish order reversed is a schedule too. Either way, a cycle is the one thing that makes a schedule impossible, and both methods notice it.
Order the vertices so every edge points forward. Each vertex shows how many edges come into it: its in-degree, the number of things that must come first. Vertices at 0 are ready. Place one, and every edge out of it lowers a neighbour's count; a neighbour that hits 0 becomes ready.
Check your understanding
The player pauses before each decision in this run and asks what happens next. Here are all 6, with their answers.
Ready queue: 0. Which vertex is placed next?
Answer: 0. Any ready vertex would be valid. This run takes them in the order they became ready.
Ready queue: 1 2. Which vertex is placed next?
Answer: 1. Any ready vertex would be valid. This run takes them in the order they became ready.
Ready queue: 2. Which vertex is placed next?
Answer: 2. Any ready vertex would be valid. This run takes them in the order they became ready.
Ready queue: 3 5. Which vertex is placed next?
Answer: 3. Any ready vertex would be valid. This run takes them in the order they became ready.
Ready queue: 5 4. Which vertex is placed next?
Answer: 5. Any ready vertex would be valid. This run takes them in the order they became ready.
Ready queue: 4. Which vertex is placed next?
Answer: 4. Any ready vertex would be valid. This run takes them in the order they became ready.
How it runs, step by step
Order the vertices so every edge points forward. Each vertex shows how many edges come into it: its in-degree, the number of things that must come first. Vertices at 0 are ready. Place one, and every edge out of it lowers a neighbour's count; a neighbour that hits 0 becomes ready.
Kahn's algorithm. Each vertex shows its in-degree. 1 vertices start ready.
Place 0, position 1. Its edges to 1, 2 are satisfied, so their counts drop. 1, 2 reached 0 and are ready.
Vertex 0 is placed at position 1. 2 vertices become ready.
Place 1, position 2. Its edges to 3 are satisfied, so their counts drop. None reached 0 yet.
Vertex 1 is placed at position 2. 0 vertices become ready.
Place 2, position 3. Its edges to 3, 5 are satisfied, so their counts drop. 3, 5 reached 0 and are ready.
Vertex 2 is placed at position 3. 2 vertices become ready.
Place 3, position 4. Its edges to 4 are satisfied, so their counts drop. 4 reached 0 and is ready.
Vertex 3 is placed at position 4. 1 vertices become ready.
Place 5, position 5. It points nowhere, so nothing changes.
Vertex 5 is placed at position 5. 0 vertices become ready.
Place 4, position 6. It points nowhere, so nothing changes.
Vertex 4 is placed at position 6. 0 vertices become ready.
Topological order: 0, 1, 2, 3, 5, 4. Every edge now points from an earlier position to a later one. Each vertex was placed once and each edge lowered one count: O(V + E).
The order is 0, 1, 2, 3, 5, 4.
Remember
- Kahn: track in-degrees, place a zero, decrement its neighbours, repeat. Leftovers mean a cycle.
- DFS: reverse postorder. An edge into a vertex still on the current path is a cycle.
- Reach for it on dependency ordering and can-everything-finish questions.
Related
Where this is used
SpreadsheetsSpreadsheet recalculation
A workbook is a graph where each formula cell has an edge from every cell it reads. Excel and Google Sheets keep that dependency graph and recalculate in topological order, so no cell is ever computed from a stale precedent and one edit only touches what is downstream of it. The circular reference warning is the cycle check firing: there is no order that puts every cell after its inputs, so the engine refuses rather than looping.
Operationssystemd boot ordering
Each systemd unit declares Before= and After= relations, which makes a Linux boot a set of jobs with prerequisites instead of a fixed script. systemd orders the jobs of a transaction against those relations and starts everything whose prerequisites are already satisfied at once, so two units with no ordering relation between them come up in parallel rather than in sequence. Write a loop of After= lines and the journal prints 'Found ordering cycle' along with the job it deleted to break it - with no legal order available it drops an edge and carries on.
Data engineeringWorkflow schedulers
An Apache Airflow DAG is a set of tasks with upstream dependencies, and by default the scheduler queues a task only after every upstream task has succeeded. That is the in-degree counter running over hours instead of microseconds: a finished task decrements its downstream counters and whatever reaches zero becomes runnable. Airflow rejects a cyclic definition when the file is parsed, for the same reason a spreadsheet does - a cycle has no run order at all.
Developer toolsParallel builds
Ninja and make -j need more than a valid build order, they need to know what may run at the same time, and the ready set answers that directly. Every target with no unbuilt prerequisite is safe to start right now, so the size of the frontier is the parallelism available at that moment. A project whose dependencies form a long chain keeps that frontier one job wide, which is why throwing more cores at it changes almost nothing.
Why it works this way
Why in-degree counters instead of hunting for a vertex with no incoming edges
The literal reading of Kahn's algorithm is: scan the graph for a vertex nothing points at, remove it, scan again. That is correct and it costs V passes over the whole graph. The counter turns the scan into bookkeeping - one pass counts every incoming edge up front, and after that each edge is walked once more, when its source is placed, to decrement exactly one counter. A vertex joins the ready queue at the instant its last prerequisite is placed, so nothing is ever rescanned and the total work stays at V + E.
Why reverse postorder, and not the order DFS visits in
Visit order is wrong and a two-edge graph shows it. With a -> c and b -> c, a DFS that starts at a emits a then c, and only afterwards reaches b, so c lands before b even though the edge b -> c demands the opposite. The fix is to append a vertex on the way out rather than on the way in, because by then everything reachable from it is already in the list and it is guaranteed to sit after all of them. Reversing at the end turns that guarantee into the one a schedule needs.
A single visited flag reports cycles that are not there
The three states are not decoration. An edge into a finished vertex (state 2) is harmless - it was reached earlier down another branch and everything below it is already placed. Only an edge into a vertex still open on the current path (state 1) is a back edge, and only a back edge is a cycle. Collapse the two into one visited boolean and an ordinary diamond, a -> b, a -> c, b -> d, c -> d, gets rejected as cyclic the second time d is reached.
The order is not unique, and your container picks which one you get
Every vertex sitting in the ready set is a legal next choice, so most graphs have many valid orders and a test asserting one exact list is testing the deque, not the algorithm. Swap the ArrayDeque for a min-heap and you get the lexicographically smallest order, which is what a problem asks for when it wants one deterministic answer; a stack generally gives a different valid order again. Check a result by confirming it lists every vertex once and that every edge points forwards in it, never by comparing against a single expected list.
Read more
- Topological sortingWikipedia
- Topological sortingcp-algorithms
- Checking a graph for acyclicity and finding a cyclecp-algorithms
- systemd.unit: Before= and After= orderingfreedesktop.org
- Course ScheduleCSES 1679 · cses.fi