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.
The problem it solves
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
Repeatedly take a vertex with no remaining incoming edges — nothing left that must come first — and remove it.
from collections import deque
def topo_sort(graph, nodes):
indegree = {n: 0 for n in nodes}
for u in graph:
for v in graph[u]:
indegree[v] += 1
queue = deque([n for n in nodes if indegree[n] == 0])
order = []
while queue:
u = queue.popleft()
order.append(u)
for v in graph.get(u, []):
indegree[v] -= 1 # u is done; one fewer prerequisite
if indegree[v] == 0:
queue.append(v)
if len(order) != len(nodes):
raise ValueError("cycle detected") # some nodes never reached indegree 0
return order
The final check is the cycle detection, and it is elegant: if a cycle exists, every vertex in it always has at least one unremoved predecessor, so none ever reaches indegree zero and the output is short. No separate cycle search is needed.
O(V + E) time, and the structure is BFS-shaped — which is why it is easy to reason about and easy to parallelise.
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.
Ordering things that depend on each other
A topological sort produces a linear ordering of a directed graph's vertices such that every edge points forwards — if A must happen before B, A appears earlier.
That is the answer to every dependency question: build order, task scheduling, module loading, course prerequisites.
Given dependencies A→C, B→C, C→D, one valid order is A, B, C, D. So is B, A, C, D. The ordering is not unique, and any order respecting all the edges is correct — which matters, because it means two implementations can disagree and both be right.
The requirement is that the graph is a directed acyclic graph. A cycle means a circular dependency, and no valid ordering exists — A before B before C before A is unsatisfiable. Detecting that is part of the algorithm's job.
DFS with finishing times
The alternative uses depth-first search: run DFS, and prepend each vertex to the output when it finishes (after all its descendants).
def topo_sort_dfs(graph, nodes):
WHITE, GREY, BLACK = 0, 1, 2
colour = {n: WHITE for n in nodes}
order = []
def visit(u):
colour[u] = GREY
for v in graph.get(u, []):
if colour[v] == GREY:
raise ValueError("cycle detected")
if colour[v] == WHITE:
visit(v)
colour[u] = BLACK
order.append(u) # append on finish
for n in nodes:
if colour[n] == WHITE:
visit(n)
return order[::-1] # reverse the finishing order
The reversal is the key insight: a vertex finishes only after everything it points to has finished, so reversing the finishing sequence puts prerequisites first.
The three-colour scheme detects cycles properly. Meeting a grey vertex means an edge back to the current path — a cycle. Meeting a black one means a finished subtree, which is fine. Using a single visited set conflates the two and reports cycles that do not exist.
Kahn's
DFS
Structure
Queue, BFS-like
Recursion, DFS
Cycle detection
Output length is short
Grey vertex encountered
Parallelisable
Yes — all indegree-0 nodes are independent
No
Recursion depth risk
None
Yes, on deep graphs
Lexicographic order
Use a heap instead of a queue
Awkward
The order, the ambiguity, and the cycle it has to reject
A topological sort answers "what order can these be done in", and two things about it surprise people: the answer is usually not unique, and the algorithm's real job is often detecting that there is no answer at all. Both are visible on a small dependency graph.
example_01.pyPython
from collections import deque
DEPS = {
"boil water": [],
"grind beans": [],
"brew": ["boil water", "grind beans"],
"warm cup": [],
"pour": ["brew", "warm cup"],
"drink": ["pour"],
}
def kahn(deps, tie_break=sorted):
indeg = {n: len(d) for n, d in deps.items()}
out_edges = {n: [] for n in deps}
for node, ds in deps.items():
for d in ds:
out_edges[d].append(node)
ready = tie_break([n for n, k in indeg.items() if k == 0])
order = []
while ready:
node = ready.pop(0)
order.append(node)
for nxt in out_edges[node]:
indeg[nxt] -= 1
if indeg[nxt] == 0:
ready.append(nxt)
ready = tie_break(ready)
return order, len(order) == len(deps)
order, ok = kahn(DEPS)
print("one valid order:")
for i, step in enumerate(order, 1):
print(" %d. %s" % (i, step))
# Now the same graph with the ready-list drained in the opposite order.
order2, _ = kahn(DEPS, lambda x: sorted(x, reverse=True))
print()
print("another valid order:", " | ".join(order2))
print("same graph, both correct:", order != order2)
# Three tasks have no prerequisites at all, so nothing in the problem
# says which comes first. A topological sort returns SOME order consistent
# with the constraints, not the order -- and code that depends on getting
# a particular one is depending on a tie-break that is not specified.
#
# What IS guaranteed is the constraint itself. Check it directly:
pos = {n: i for i, n in enumerate(order)}
violations = [(d, n) for n, ds in DEPS.items() for d in ds if pos[d] > pos[n]]
print()
print("dependencies that came after the task needing them:", violations)
# Empty, in both orders. That is the entire specification.
#
# And the case with no answer. Add one edge that makes a cycle:
CYCLIC = dict(DEPS)
CYCLIC["boil water"] = ["drink"] # you must drink before you boil
order3, ok3 = kahn(CYCLIC)
print()
print("with a cycle, Kahn's algorithm produced %d of %d tasks" % (
len(order3), len(CYCLIC)))
print("complete?", ok3)
print("stuck on:", sorted(set(CYCLIC) - set(order3)))
# It did not loop forever and it did not raise: it simply ran out of
# tasks with an in-degree of zero, and the count came up short. That
# comparison -- did I emit every node? -- IS the cycle detection, and it
# comes free with the algorithm.
#
# Which is why this is the check behind "circular dependency detected" in
# build systems, package managers and spreadsheet engines: they are all
# running a topological sort, and the error is the sort failing to finish.
Output
Things to try
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.
Summing up
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.
Where it is used
Build systems.make, Bazel, Gradle and every dependency-aware build tool topologically sorts targets. A circular dependency is reported as an error, and that error is this algorithm's cycle detection.
Package managers. Installing dependencies before the things that need them.
Task and job scheduling in workflow engines — Airflow DAGs are named after the requirement.
Spreadsheet recalculation. Cells depend on other cells; a circular reference error is a detected cycle.
Compiler passes and module initialisation order.
Course prerequisites and curriculum planning.
Database migrations applied in dependency order.
Dynamic programming on a DAG, where the topological order is the correct evaluation order.
That last one is worth expanding: on a DAG, processing vertices in topological order guarantees that a vertex's dependencies are already computed. Longest path in a DAG — NP-hard in a general graph — becomes linear this way.
Choosing among valid orders
Because many orderings are valid, applications often want a specific one.
Lexicographically smallest. Replace Kahn's queue with a min-heap, so the smallest available vertex is always taken next. Useful when output must be deterministic and reproducible.
Maximum parallelism. Kahn's algorithm naturally produces levels: all vertices with indegree 0 at the start can run simultaneously, then their successors, and so on. Grouping by level rather than emitting a flat list gives the schedule with the shortest critical path.
def topo_levels(graph, nodes):
indegree = compute_indegrees(graph, nodes)
level = [n for n in nodes if indegree[n] == 0]
levels = []
while level:
levels.append(level)
nxt = []
for u in level:
for v in graph.get(u, []):
indegree[v] -= 1
if indegree[v] == 0:
nxt.append(v)
level = nxt
return levels
That levelled form is what a build system uses to decide what can compile in parallel, and it is a small change from the standard algorithm.
Common mistakes
Not detecting cycles. Without the length check, a cyclic graph silently produces a partial ordering that looks valid.
Using a single visited set in the DFS version, which cannot distinguish a back edge from a cross edge and reports false cycles.
Forgetting isolated vertices. A vertex with no edges never appears in an edge list and must be added explicitly.
Assuming the order is unique and writing tests that expect one specific sequence.
Applying it to an undirected graph, where the concept does not apply.
Recursion depth in the DFS version on a long chain.
Questions people ask
What if the graph has a cycle? No topological order exists. Kahn's algorithm produces a short output; the DFS version hits a grey vertex.
Is the order unique? Only when the graph is a single chain. Otherwise many valid orders exist.
Kahn's or DFS? Kahn's for parallel scheduling, lexicographic control and no recursion limit. DFS when you are already doing a DFS or need finishing times for something else.
How do I get a deterministic order? Use a heap instead of a queue in Kahn's algorithm.
Can it handle disconnected graphs? Yes — all indegree-0 vertices seed the queue, whichever component they are in.
How is this related to DFS cycle detection? They are the same traversal; topological sort is the finishing order, and a back edge to a grey vertex is the cycle.
Recap in one screen
Order the vertices so every edge points forwards — the answer to every dependency question.
Requires a DAG; a cycle means no valid order exists, and the algorithm detects it.
Kahn's repeatedly removes indegree-0 vertices; a short output means a cycle.
DFS prepends each vertex on finishing, and needs three colours to detect cycles correctly.
Grouping Kahn's output into levels gives the maximum-parallelism schedule, which is what build systems use.
Run it in Python
Kahn's algorithm on a small course-prerequisite graph, printing the in-degree table as it drains. The final block adds one edge that closes a cycle, which is how the same code detects that no ordering exists.
topological_sort.pyPython 3
# Topological sort (Kahn): repeatedly take a node nothing depends on.
from collections import deque
prereqs = {
"intro": [],
"maths": [],
"python": ["intro"],
"data": ["python", "maths"],
"ml": ["data", "maths"],
"deep": ["ml"],
"nlp": ["deep"],
}
def topological_sort(prereqs):
indegree = {n: len(deps) for n, deps in prereqs.items()}
dependents = {n: [] for n in prereqs}
for node, deps in prereqs.items():
for d in deps:
dependents[d].append(node)
ready = deque(n for n, deg in indegree.items() if deg == 0)
print("start, in-degrees:", indegree)
order = []
while ready:
node = ready.popleft()
order.append(node)
for dependent in dependents[node]:
indegree[dependent] -= 1 # one prerequisite satisfied
if indegree[dependent] == 0:
ready.append(dependent)
print(f"take {node:>7} -> ready={list(ready)}")
if len(order) != len(prereqs): # something never reached zero
stuck = [n for n, deg in indegree.items() if deg > 0]
return None, stuck
return order, []
order, stuck = topological_sort(prereqs)
print()
print("a valid order:", " -> ".join(order))
print()
print("Now make nlp a prerequisite of maths, which closes a cycle:")
prereqs["maths"] = ["nlp"]
order, stuck = topological_sort(prereqs)
print("order:", order)
print("never reached in-degree 0:", stuck)
Output
How the code works
indegree = {n: len(deps) for n, deps in prereqs.items()}How many prerequisites each node is still waiting on. The algorithm is nothing but keeping this table correct as nodes are removed.
dependents[d].append(node)The graph reversed. The input says “what does this need”; the loop needs “what is unblocked when this is done”, and building both is cheaper than searching one repeatedly.
ready = deque(... if deg == 0)Everything with no prerequisites can start immediately, and in any order. A graph usually has many valid topological orders, not one.
indegree[dependent] -= 1Decrement, never recompute. Each edge is looked at exactly once across the whole run, which is what makes this O(V + E).
if len(order) != len(prereqs):The cycle test, and it is free. Nodes in a cycle always wait on each other, so their in-degree never reaches zero and they never enter the queue — a short output is the detection.
Change one thing
Swap popleft() for pop(). A different, equally valid order comes out — useful proof that the answer is not unique.
Use a heapq instead of a deque to get the lexicographically smallest valid order. That is the usual “deterministic build order” requirement.
Add a node with a prerequisite on itself. In-degree 1 forever, and it shows up in the stuck list immediately.
Where this runs
Real CPython, compiled to WebAssembly and running on your own machine — nothing is uploaded. The first run takes a few seconds while the interpreter downloads; after that it is immediate. Need more room, or want to paste your own attempt? Use the Python compiler.
Check yourself
0 of 3
Answer without scrolling back up.
Kahn's algorithm starts from the nodes whose in-degree is:
In-degree zero means nothing has to happen first, so those can be taken immediately - and in any order among themselves.
The program detects a cycle by noticing that:
Nodes in a cycle wait on each other forever, so their in-degree never reaches zero and they never enter the queue. The short output is the detection - it costs nothing extra.
A directed acyclic graph has:
Swapping popleft() for pop() produces a different, equally correct order. Where a specific one is needed, a heap gives the lexicographically smallest.
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.
Ashish Jangra builds and maintains VizLearn. Every module here is written and the visualisation behind it hand-built, so the numbers in a readout come from the same code that draws the picture. Corrections are genuinely welcome and get priority over everything else — if a page states something wrong, or an animation misrepresents what the algorithm does, get in touch.