Algorithms · Topological sort

Topological sort

Ordering a dependency graph so nothing comes before what it needs: Kahn's algorithm with in-degrees, the DFS version, cycle detection, controlling the order, and parallel levels.

Updated 2026-09-21

On this page

Some things have to happen before others. Compile this file before that one, take this course before that one, install this package before that one. A topological sort takes that tangle of "before" relationships and flattens it into a single order that never breaks one of them — or tells you that no such order exists.

The map

Read this first when short on time. Every branch is a section below.

Figure 1. The whole article on one page. Every branch is a section below; fold what you know, open what you do not.

What it is

You have a directed graph where an arrow from A to B means "A must come before B". A topological sort is any arrangement of the nodes in a line such that every arrow points forward.

Figure 2. A and B depend on nothing, so either may go first. C needs A, D needs both A and B, E needs C and D, F needs E. Several orders satisfy all of that, and any of them is a correct answer.

Two properties follow immediately, and both matter in practice.

The graph must have no cycles. If A must come before B and B must come before A, no line can satisfy both. A directed graph with no cycles is a DAG, and a topological sort exists exactly when the graph is one. This means the sorting algorithm is also a cycle detector, which is usually the more valuable output — a build system finding a circular import needs to report it, not order around it.

The answer is usually not unique. In the figure, A and B are independent, so either can go first; the order shown and B A D C E F are both correct. If you need a stable, reproducible answer — and build systems do — you have to pin the choice down deliberately, which the section below covers.

Kahn's algorithm

The intuition is how you would actually do it by hand. Look for something with nothing blocking it. Take it. Cross out its arrows, which may free up something else. Repeat.

"Nothing blocking it" means in-degree zero — no arrows pointing in. So:

Count in-degrees. One pass over all the edges.
Queue every node with in-degree zero. These can go first, in any order.
Pop one, append it to the output. For each of its outgoing edges, decrement the target's in-degree; if that hits zero, push the target.
Repeat until the queue is empty.

from collections import deque

def topo_sort(graph):
    indeg = {n: 0 for n in graph}
    for u in graph:
        for v in graph[u]:
            indeg[v] += 1

    q = deque(n for n in graph if indeg[n] == 0)
    order = []

    while q:
        u = q.popleft()
        order.append(u)
        for v in graph[u]:
            indeg[v] -= 1              # u is placed, so it no longer blocks v
            if indeg[v] == 0:
                q.append(v)

    if len(order) != len(graph):
        raise ValueError("cycle: " + str([n for n in graph if indeg[n] > 0]))
    return order

Running it on Figure 2 — starting in-degrees are A:0, B:0, C:1, D:2, E:2, F:1:

Step	Popped	Reached in-degree 0	Queue after	Output so far
1	A	C	B C	A
2	B	D	C D	A B
3	C	— (E still needs D)	D	A B C
4	D	E	E	A B C D
5	E	F	F	A B C D E
6	F	—	empty	A B C D E F

Cycle detection is free. If the graph has a cycle, the nodes in it never reach in-degree zero — each is always waiting on another — so the queue empties early and the output is short. Comparing the output length with the node count is the whole test, and the nodes left with a positive in-degree are exactly the ones caught in or blocked by the cycle, which makes a genuinely useful error message.

Cost is O(V + E): one pass to count in-degrees, and then each node enters and leaves the queue once while each edge is decremented once.

The DFS version

There is a second route, and it comes straight from the DFS idea of exit times.

When DFS finishes a node — when it has explored everything that node can reach — every one of its dependents is already finished. So finish order is reverse dependency order. Record nodes as they finish and reverse the list at the end.

def topo_sort_dfs(graph):
    UNSEEN, IN_PROGRESS, DONE = 0, 1, 2
    state = {n: UNSEEN for n in graph}
    out = []

    def visit(u):
        state[u] = IN_PROGRESS
        for v in graph[u]:
            if state[v] == IN_PROGRESS:
                raise ValueError("cycle through " + str(v))
            if state[v] == UNSEEN:
                visit(v)
        state[u] = DONE
        out.append(u)                  # append on the way OUT

    for n in graph:
        if state[n] == UNSEEN:
            visit(n)
    return out[::-1]                   # reverse

On the same graph this produces the finish order F E C D A B, which reversed is B A D C E F — a different valid answer from Kahn's, which is exactly the non-uniqueness described above.

Watch out

The reversal is not optional and it is the most common bug here. Appending on the way in gives you dependents before dependencies — precisely backwards — and on a small graph the result can look plausible enough to pass a quick check.

Which one to use

They cost the same and produce equally valid answers, so choose on the surrounding details.

	Kahn (in-degrees)	DFS (reverse finish order)
Shape	Iterative, a queue	Recursive, the call stack
Cycle detection	Output shorter than node count	Edge to an in-progress node
Naming the cycle	Leftover nodes, but not the loop itself	The current path is the loop
Deep graphs	Safe	Can overflow the stack
Controlling the order	Natural — swap the queue for a heap	Awkward
Parallel levels	Natural — drain a level at a time	Not available

Kahn's is the better default for real systems: it cannot overflow, the cycle check is a comparison of two numbers, and it extends cleanly to the two features below. DFS wins on brevity, and when a cycle is found it can report the actual loop, because the nodes currently in progress are the cycle.

Controlling the order, and finding parallel work

Two extensions to Kahn's that come up constantly, both one small change.

A deterministic order. A queue picks arbitrarily among the available nodes, so the output can vary between runs. Swap the queue for a min-heap and you always take the smallest available node, which gives the lexicographically smallest valid order — reproducible, diffable, and worth the extra log factor whenever the output is compared between runs.

import heapq
q = [n for n in graph if indeg[n] == 0]
heapq.heapify(q)
# ... heapq.heappop(q) and heapq.heappush(q, v) instead of popleft and append

Parallel levels. Everything with in-degree zero at the same moment has no dependency on anything else available, so it can all run at once. Drain the queue one full level at a time — record its length, pop exactly that many — and each batch is a set of tasks that can run in parallel.

Figure 3. Levels turn a topological sort into a schedule. The number of levels is the longest chain of dependencies, which is the fastest the whole job can possibly finish no matter how many machines you have.

That last line is worth remembering on its own: the number of levels is the critical path, and no amount of parallelism beats it. If a build takes twelve levels, twelve sequential steps is the floor.

Where it shows up

In the wild

Build systems. Make, Bazel, Gradle and every module bundler compute a topological order over file or module dependencies, and report a circular import as an error rather than trying to resolve it.
Package managers. Installing in dependency order is a topological sort; a dependency cycle between packages is a known, awkward failure that has to be broken by hand.
Task and data pipelines. Airflow and similar schedulers are explicitly DAGs of tasks, and the level trick above is exactly how they decide what can run concurrently.
Spreadsheet recalculation. Cells depend on other cells, so recalculating in topological order computes each one exactly once — and the circular-reference warning is the cycle check.

Recap

A topological sort flattens a dependency graph into a line where every arrow points forward, so nothing appears before something it needs.
It exists exactly when the graph is a DAG. A cycle means no valid order, so the sort doubles as a cycle detector — usually the more useful output.
The answer is normally not unique; independent nodes can go in either order, and every such arrangement is correct.
Kahn's algorithm: count in-degrees, queue the zeros, pop one, append it, decrement its neighbours, push any that reach zero.
Kahn detects cycles by counting — if the output is shorter than the node list, the remaining nodes are stuck in or behind a cycle.
The DFS version appends each node as it finishes and reverses the result, because a node finishes only after everything it depends on.
Forgetting the reversal is the classic DFS bug, and it produces an order that is exactly backwards.
Both are O(V + E). Choose on the extras: Kahn cannot overflow the stack and controls order easily; DFS is shorter and can name the actual cycle it found.
For a deterministic, reproducible order, replace Kahn's queue with a min-heap to get the lexicographically smallest valid order.
Draining the queue one full level at a time gives batches of tasks that can run in parallel.
The number of levels is the critical path — the minimum number of sequential rounds, no matter how many workers you have.
It appears wherever "this before that" does: build systems, package installation, task schedulers and spreadsheet recalculation.

Questions

Try answering each one out loud before opening it. Lead with the one-line answer, then the reasoning, then one detail that shows depth.

What is a topological sort, and when does one exist?

An arrangement of a directed graph's nodes in a line such that every edge points forward. One exists exactly when the graph has no directed cycle — that is, when it is a DAG.

An edge from A to B means A must come before B, so a cycle demands that a node precede itself.
The sorting algorithm therefore doubles as a cycle detector.
The order is usually not unique, since independent nodes can be placed in either order.

In practice the cycle answer is often the one that matters more — a build system needs to report a circular import, not work around it.

Explain Kahn's algorithm.

Count how many edges point into each node, queue every node with a count of zero, then repeatedly pop one, append it to the output, and decrement the counts of its targets — pushing any that reach zero.

In-degree zero means nothing is blocking that node, so it is safe to place next.
Removing a node frees its dependents, which is what the decrement represents.
Cost is O(V + E): one pass to count, then each node and edge handled once.

It is the mechanical version of how a person would do it by hand: find something with no prerequisites, take it, cross out its arrows, repeat.

How does Kahn's algorithm detect a cycle?

By counting the output: nodes inside a cycle never reach in-degree zero, because each is always waiting on another, so the queue empties early and fewer than n nodes are produced.

The nodes left with a positive in-degree are those in the cycle or blocked behind it.
That set makes a far better error message than a bare failure.
It does not identify the exact loop, only the region containing it.

A comparison of two integers detecting a structural property of the graph is one of the tidier results in this area.

How does the DFS version work, and why does it need a reversal?

Run DFS and append each node when it finishes; since a node finishes only after everything it can reach has finished, the finish order lists dependents before dependencies — so reversing it gives the topological order.

Appending on the way in rather than out produces exactly the wrong order.
Cycle detection uses the three-state marking from DFS: an edge to an in-progress node closes a loop.
Because the in-progress nodes form the current path, DFS can report the actual cycle.

This is the clearest practical payoff of DFS's exit times, which is why the two articles are worth reading together.

Kahn or DFS?

Kahn's for production systems and DFS for brevity. Kahn is iterative so it cannot overflow the stack, its cycle check is a length comparison, and it extends naturally to deterministic ordering and parallel levels.

Both are O(V + E) and both are correct, so speed is not the deciding factor.
DFS can name the cycle it found, which Kahn cannot.
DFS risks a stack overflow on a long dependency chain.

If you are already walking the graph with DFS for another reason, taking the order from the same pass is free.

Why is the answer usually not unique, and how do you make it deterministic?

Because at any point several nodes may have in-degree zero and any of them is a legal next choice; a plain queue picks arbitrarily. Replacing it with a min-heap always takes the smallest available node and yields the lexicographically smallest valid order.

Determinism matters whenever output is compared between runs — build caches, diffs, reproducible artefacts.
The heap costs a log factor, giving O((V + E) log V).
Any tie-break rule works; smallest-first is just the conventional one.

A non-deterministic order is a real source of confusing build-cache misses, so it is worth pinning down early.

How do you find which tasks can run in parallel?

Drain the queue one full level at a time: record its length, pop exactly that many nodes, and treat that batch as tasks with no dependency on each other, so they can all run at once.

Everything with in-degree zero at the same moment is mutually independent by definition.
The number of levels is the longest dependency chain, the critical path.
No amount of parallelism finishes the job in fewer rounds than that.

This is exactly how a task scheduler decides what to dispatch concurrently, and why shortening the critical path matters more than adding machines.

Your build system reports a circular dependency. How would you find and present it?

Use the DFS version, because the set of in-progress nodes at the moment the back edge is found is the cycle itself — so you can print the actual chain rather than a list of affected files.

Kahn tells you which nodes are stuck but not the loop's order.
Slicing the current path from the repeated node to the end gives the loop precisely.
Reporting file names in loop order is dramatically more actionable than a generic error.

This is the main reason to keep the DFS version around even when Kahn's is the default.

Course scheduling: you have courses and prerequisite pairs. How do you check the plan is possible?

Build a graph with an edge from each prerequisite to the course requiring it, run a topological sort, and check that every course appears in the output — if any are missing, the prerequisites are circular and no schedule exists.

Getting the edge direction right is the main trap: it goes from prerequisite to dependent.
The order produced is a valid term-by-term plan.
Using levels instead tells you the minimum number of terms needed.

That last variant is the more interesting question, and it is the same critical-path idea as in a build.

What happens if the graph is disconnected?

Nothing special — a topological sort does not require connectivity. Kahn's starts with every in-degree-zero node across all components, and the DFS version loops over all unvisited nodes.

Independent components are interleaved arbitrarily in the output, which is valid since there are no edges between them.
Isolated nodes with no edges at all simply appear somewhere in the order.
Forgetting the outer loop in the DFS version silently omits entire components.

That omission is easy to miss because the output still looks like a valid order — it is just incomplete.

How would you handle a graph too large to hold in memory?

Kahn's adapts better: in-degrees can be computed in a streaming pass over the edges, and the algorithm only needs the current frontier of zero in-degree nodes plus the counts, rather than the whole structure at once.

The edge list can be stored externally and read in passes.
The DFS version needs random access to adjacency lists and a stack proportional to the longest path.
The frontier can still be large, so this helps with edges more than with nodes.

Large-scale systems usually partition the graph and sort within partitions, then order the partitions themselves.

What if edges have weights, such as task durations?

The topological order still comes first, then you sweep it once to compute earliest start times: each node's start is the maximum finish time among its predecessors. The largest finish time overall is the project duration.

Processing in topological order guarantees every predecessor is already computed when you reach a node.
This is the critical path method, and the chain achieving the maximum is the critical path.
Longest paths in a DAG are easy for the same reason, unlike in a general graph where they are intractable.

That a DAG makes longest-path computation easy is a good reminder that acyclicity buys far more than just an ordering.