Ordering What Depends on What
In short: a topological order lists every job so each one's needs come before it. Kahn's algorithm builds one by counting, for each job, how many needs it's still waiting on — its in-degree — and emitting any job whose count reaches zero. Emitting a job lowers its dependants' counts, which can make more jobs ready, so the queue keeps feeding itself until it runs dry. If jobs are left over when it does, they wait on each other in a cycle, and no order exists.
Welcome to Meridian, a city logistics network. It has depots, roads, one-way streets, vans, drivers and jobs, and over the next few sections you will build the software that runs it. This section builds Meridian's model of the city: what the network is made of, which parts hold it together, and where it is fragile. Routing parcels through it comes later. First, the network has to exist.
Meridian is opening a depot in the north of the city, and the build-out is a list of jobs with strings attached. The site has to be surveyed before it can be graded. Grading also needs a permit. Paving waits for grading, and the traffic signals wait for both the paving and the permit. Five jobs, five "this before that" rules, and one question: in what order can the crews work?
Needs are directed edges
Draw each job as a node and each rule [before, after] as an arrow from before
to after. The result is a directed graph, and it is the same adjacency-list
shape you used for the follow graph in the graphs section, with one extra number
per node: how many arrows point into it. That count is the node's
in-degree, and here it means "how many jobs am I still waiting for?"
An order that puts every before ahead of its after is a topological order.
It is not unique: survey and permit have no needs at all, so either can go first.
It can also fail to exist, as you'll see shortly. Checking whether a proposed order
is valid is easy: every rule's before must sit at an earlier position.
needs = [["survey", "grade"], ["permit", "grade"], ["grade", "pave"]]
order = ["permit", "grade", "survey", "pave"]
position = {task: i for i, task in enumerate(order)}
print(all(position[a] < position[b] for a, b in needs))Kahn's algorithm: emit what nothing is waiting on
Here is the whole idea. A job with in-degree 0 waits on nothing, so it can go first. Once it's done, every job that was waiting on it has one fewer thing to wait for, so subtract one from each of their counts. Any count that reaches zero is a job that just became ready. Keep going until nothing is ready.
This is Kahn's algorithm, and it's easier to watch than to read. Each badge is a job's current in-degree; the highlighted jobs are ready, and the note underneath is the order being built:
Kahn's algorithm only ever emits a job whose badge is 0, and emitting it lowers the badges of the jobs waiting on it.
Count the arrows into each job. Survey and permit wait on nothing, so both are ready. 5 nodes, 5 edges, directed. Frontier: survey, permit. survey: 0, permit: 0, grade: 2, pave: 1, signals: 2.
In code, the "ready" set is a queue. Any queue gives a valid order; which one you get depends on the order ready jobs come out:
Every job enters the queue once and every rule is looked at once, when its
before job is emitted. That makes Kahn's algorithm O(V + E) for V jobs and E
rules: the same cost as reading the input. Space is O(V + E) too — the after
map holds every rule once, and waiting and the queue hold at most one entry per job.
from collections import deque
after = {"a": ["c"], "b": ["c", "d"], "c": ["e"], "d": ["e"], "e": []}
waiting = {"a": 0, "b": 0, "c": 2, "d": 1, "e": 2}
queue = deque(["b", "a"])
order = []
while queue:
task = queue.popleft()
order.append(task)
for nxt in after[task]:
waiting[nxt] -= 1
if waiting[nxt] == 0:
queue.append(nxt)
print(" ".join(order))When nothing can be emitted
Now suppose someone adds a rule by mistake: grading can't start until the signals are up. Signals already wait on paving, which waits on grading. Watch what Kahn's algorithm does with that:
A cycle is exactly what Kahn's algorithm leaves behind, because every job on it waits for another job on it.
The bad rule gives grade a third thing to wait for, and it's signals. 5 nodes, 6 edges, directed. survey: 0, permit: 0, grade: 3, pave: 1, signals: 2.
The algorithm never gets stuck silently. When the queue runs dry you just count: if fewer jobs came out than went in, the leftovers contain a cycle and there is no valid order. That count is the only change the main task needs. Leave it out and you ship a schedule missing three jobs, with nothing to say why.
A classic slip
This version is almost right. Run it in your head on three jobs: survey and permit both come before grade.
This prints grade twice, and on a longer chain it would start grade before permit finished. Fix it so every job appears once, after everything it needs.
Step through the correct loop on a smaller build and watch waiting count down:
Your turn to drive it
Here is Kahn's algorithm again, drawing every step with the in-degrees as badges.
Add a rule to needs (try ["signals", "survey"]) and run it again to see what a
cycle leaves on screen:
Your Kahn's algorithm. A badge only ever goes down, and a job is emitted the moment its badge reaches 0.
Why not just keep scanning?
The obvious approach without in-degrees is to scan the task list for any task whose needs are all done, emit it, and scan again. Each scan reads every task and every rule, and you scan once per task, so it costs about V × (V + E). Kahn's keeps a running count instead and never rescans. If each job has about two rules, one scan costs about 3n steps:
| jobs n | rescanning (3n²) | Kahn's (3n) |
|---|---|---|
| 100 | 30,000 | 300 |
| 580 | about 1 million | 1,740 |
| 5,000 | 75 million | 15,000 |
Rescanning passes a million steps at about 580 jobs, and the gap only widens, because Kahn's algorithm touches each job and each rule once.
The other way: depth-first finish order
Depth-first search gives a topological order too. Run DFS, and write each job down when you finish it, meaning everything reachable from it has been finished. A job always finishes after the jobs that wait on it, so the finish order is a valid order reversed. The version below uses an explicit stack, so a 10,000-job chain can't hit Python's recursion limit:
This version does not notice cycles. It happily returns an order for a circular set of rules. Detecting them during DFS is the next lesson.
❓ Cross-question: "Which should I use?" Kahn's when you want the cycle check for free, want to control ties (as the main task does), or want waves of parallel work. DFS when you are already doing a DFS for another reason. Both are O(V + E).
Idioms & real-world patterns
A heap makes the order predictable
Swap the deque for a heap and heappop always hands you the smallest ready name.
The order is then the same on every run and every machine, which matters when
a schedule is shown to people or compared in a test. It costs O(log V) per job.
The standard library has one
graphlib.TopologicalSorter takes a dict mapping each node to the nodes it
depends on (the reverse of after), and raises CycleError naming a cycle:
Build tools, package managers, spreadsheet recalculation and database migrations all order their work this way.
⚡ Advanced: the longest chain
Waves of ready jobs give the fewest days with unlimited crews. Give each job a duration and the same pass, in topological order, computes the earliest finish: each job starts when the slowest thing it needs finishes. The chain that sets the finish date is the critical path, and it's the capstone exercise below.
Quick practice
tasks = ["a", "b", "c", "d"]
needs = [["a", "b"], ["a", "c"], ["b", "d"], ["c", "d"]]
waiting = {t: 0 for t in tasks}
for before, later in needs:
waiting[later] += 1
print(waiting["d"])This prints just ['grade'], because survey and permit never reach a count of 0. Fix which task's count gets incremented.
🎯 Your turn
Write build_order(tasks, needs). Return every task in an order that respects each
[before, after] pair, taking the alphabetically first task whenever several
are ready, and return [] when the needs are circular:
build_order(["pave", "grade", "survey"], [["survey", "grade"], ["grade", "pave"]])→["survey", "grade", "pave"]build_order(["a", "b"], [["a", "b"], ["b", "a"]])→[]
Hint: Kahn's algorithm with a heap for the ready set, and a final count to catch a cycle.
Then press ▶ Run, tap the Live App try chips to call it with different inputs, and hit ✓ Check. Green = this piece of Meridian is built. ✅