Order tasks so every prerequisite comes before whatever depends on it. Build systems, course planners and package managers all run this — and it is also how they detect a circular dependency.
Controls
compute in-degree of all
queue = nodes with in-degree 0while queue:
n = queue.pop()
output(n)
for m in neighbours(n):
indeg[m] -= 1if indeg[m] == 0: queue.add(m)
Kahn's Algorithm
step 0
Output order
Insight
A node can only be output once every arrow pointing into it has been satisfied — that count is its in-degree.
In-degrees
ready queue–
output0
Complexity
TimeO(V+E)
SpaceO(V)
Needs a DAGyes
Topological Sort
Putting dependencies in a workable order — and noticing when that is impossible.
Quick Context
A topological sort orders the vertices of a directed graph so that every edge points forwards: if A must happen before B, A appears earlier. It answers "in what order can I do these dependent tasks?"
It Requires a DAG
A valid ordering exists if and only if the graph is a directed acyclic graph — directed edges, no cycles. If A depends on B and B depends on A, no order can satisfy both.
Select Circular dependency and run it: the algorithm stalls with nodes left over. That stall is the cycle detection, which is why the same code powers "circular dependency detected" errors in build tools.
Kahn's Algorithm
Count each node's in-degree — how many edges point into it.
Every node with in-degree 0 has no unmet prerequisites; put them in a ready queue.
Remove one, output it, and decrement the in-degree of everything it points to.
Any node whose in-degree hits 0 is now ready — add it to the queue.
Repeat until the queue empties.
If you output every node, you have a valid order. If the queue empties early, the remainder are locked in a cycle.
The Order Is Not Unique
Whenever the ready queue holds more than one node, any of them may go next — each choice yields a different but equally valid ordering. Watch the queue readout: when it holds several nodes, that is genuine freedom.
This is why build systems can parallelise: everything sitting in the ready queue at the same moment has no dependency on the others and can run simultaneously.
Where You Meet It Daily
Build systems — compile dependencies before dependents.
Package managers — npm, pip and apt install in dependency order and report cycles.
Spreadsheets — recalculate cells in formula-dependency order; circular references are exactly a detected cycle.
Course planning — the prerequisite example in this lab.
Task schedulers and CI pipelines — stage ordering.
Interactive Exploration Guide
Run the build pipeline. Only in-degree-0 nodes can start — those with no prerequisites at all.
Watch in-degrees fall as each node is output. A node becomes ready the moment its count reaches zero.
Note when the queue holds two or more nodes. Those tasks are independent and could run in parallel.
Switch to the circular dependency. The queue empties with nodes still unprocessed — the algorithm has proved no valid order exists.
Look at the in-degrees of the stuck nodes. None reaches zero, because each waits on another inside the cycle.
Key Takeaway
Topological sort orders a DAG so dependencies always precede dependents, in O(V+E) via in-degree counting. When it cannot output every node, the leftovers form a cycle — making it both a scheduler and a circular-dependency detector.
Cheat sheet
Topological Sort
Order tasks so every prerequisite comes before whatever depends on it. Build systems, course planners and package managers all run this — and it is also how they detect a circular dependency.