Topological Sort in Python: Ordering Tasks That Depend on Each Other

A build system has to compile utils before api, because api imports it. It does not care whether the stylesheet assets are processed before or after the config file — those two have nothing to do with each other. Topological sort is the algorithm that turns a pile of "this must happen before that" rules into one flat list you can run from top to bottom, without ever having to think about the rules again.

It has one hard requirement: the dependencies must form a directed acyclic graph — a DAG. Directed, because "before" points one way. Acyclic, because if A waits on B and B waits on A, no valid order exists. That is not a weakness of the algorithm but a property of the problem — nothing can order a circular dependency, and the only honest response is to detect it and say so. The main algorithm below detects it for free, which is much of why it is the one to learn.

Two implementations are worth knowing. Kahn's algorithm counts incoming edges and drains the graph with a queue. The depth-first variant recurses to the bottom and builds the answer backwards. Both cost O(V + E) — linear in the number of nodes plus the number of edges — and each is better than the other at something. Both are below, traced by hand and then in code.

The idea

Draw your tasks as nodes. Draw an arrow from utils to api to mean "utils must come before api". A topological order is any listing of all the nodes in which every single arrow points forwards — left to right, no exceptions.

Here is the graph used throughout this post. It is a small front-end build: a config file and an assets folder at the start, a test run at the end, and a few modules in between.

The mechanism is one sentence: repeatedly take a node that nothing is still waiting on, output it, and delete it from the graph.

To make "nothing is still waiting on it" cheap to test, count each node's in-degree — the number of arrows pointing at it. A node with in-degree 0 has no unmet dependencies, so it is safe to run right now. When you output a node and delete it, every arrow leaving it disappears too, so each of its neighbours loses one from its in-degree. Any neighbour that drops to 0 has just become safe, and joins the pool of ready work.

That is Kahn's algorithm in full. It raises an obvious question: what if, at some point, no node has in-degree 0? On a DAG that cannot happen, and the reason is a short argument worth following.

Pick any node and walk backwards along an incoming arrow, again and again. You can never step on a node twice, because a repeat would mean you had walked in a circle and the graph is acyclic. The graph is finite, so the walk must stop, and the only place it can stop is a node with no incoming arrow at all. Every non-empty DAG therefore has at least one node of in-degree 0, and deleting a node from a DAG leaves a smaller DAG. The pool is never empty until the graph is.

Watching it work

The seven nodes are config, assets, utils, api, ui, app and tests. The arrows are: config before utils and api; assets before ui; utils before api and ui; api before app; ui before app; app before tests. Eight edges.

Counting arrows into each node gives the starting in-degrees:

Two nodes start at 0, so the ready queue begins as config, assets. Now drain it, taking from the front each time:

• Take config. Output so far: config. Its two arrows go to utils (1 becomes 0 — ready) and api (2 becomes 1). Queue: assets, utils.
• Take assets. Its one arrow goes to ui (2 becomes 1). Nothing is freed. Queue: utils.
• Take utils. Its arrows go to api (1 becomes 0 — ready) and ui (1 becomes 0 — ready). Queue: api, ui.
• Take api. Its arrow goes to app (2 becomes 1). Nothing is freed yet, because app is still waiting on ui. Queue: ui.
• Take ui. Its arrow goes to app (1 becomes 0 — ready). Queue: app.
• Take app. Its arrow goes to tests (1 becomes 0 — ready). Queue: tests.
• Take tests. No outgoing arrows. Queue: empty.

Seven nodes taken out of a seven-node graph, so nothing was left stranded. The order is config, assets, utils, api, ui, app, tests, and you can check it against the eight rules one at a time: every arrow does point forwards.

Notice the moment after utils came out. Two nodes were ready at once, api and ui, and the algorithm had a genuine free choice. It took api only because that node happened to be queued first. Taking ui first would have produced a different, equally correct order. Hold on to that — it comes back below.

The code

Kahn's algorithm translates almost literally. The graph is an adjacency list: a dictionary mapping each node to the list of nodes that must come after it. If you have not met that representation, the graph representations post covers it and its alternatives.

from collections import deque

# An edge u -> v means "u must be finished before v can start".
# Every node needs its own key, even when it has no outgoing edges.
build_graph: dict[str, list[str]] = {
    "config": ["utils", "api"],
    "assets": ["ui"],
    "utils": ["api", "ui"],
    "api": ["app"],
    "ui": ["app"],
    "app": ["tests"],
    "tests": [],
}


def topological_sort_kahn(graph: dict[str, list[str]]) -> list[str]:
    """Return an order of `graph` in which every edge points forwards.

    Raises ValueError if the graph contains a cycle, because a graph with a
    cycle has no such order at all.
    """
    in_degree = {node: 0 for node in graph}
    for node, neighbours in graph.items():
        for neighbour in neighbours:
            in_degree[neighbour] += 1

    # A node with no unmet dependencies can be emitted straight away.
    ready = deque(node for node in graph if in_degree[node] == 0)
    order: list[str] = []

    while ready:
        node = ready.popleft()
        order.append(node)
        for neighbour in graph[node]:
            # Emitting `node` satisfies this edge, so the neighbour is one
            # dependency closer to being ready.
            in_degree[neighbour] -= 1
            if in_degree[neighbour] == 0:
                ready.append(neighbour)

    if len(order) != len(graph):
        raise ValueError("the graph has a cycle, so no topological order exists")
    return order


print(" -> ".join(topological_sort_kahn(build_graph)))

config -> assets -> utils -> api -> ui -> app -> tests

Exactly the order traced by hand. The deque from collections gives O(1) removal from the front; a plain list would make pop(0) shift every remaining element and quietly turn the loop quadratic.

Depth-first search, the other way round

The second approach comes at the problem from the opposite end. Instead of asking "what can I run first?", it asks "what must run last?".

Run a depth-first search from every node. When a node's recursive call is about to return — after every node reachable from it has been fully explored — append it to a list. A node therefore lands in that list only once everything downstream of it is already in there, which means the list comes out in reverse dependency order. Reverse it at the end and you have a topological order.

def topological_sort_dfs(graph: dict[str, list[str]]) -> list[str]:
    """Topological order by depth-first search: append on the way out, reverse.

    Each node is in one of three states, which is what makes cycle detection
    work: never seen, on the path currently being explored, or fully explored.
    Meeting a node that is still on the current path closes a cycle.
    """
    UNSEEN, ON_PATH, EXPLORED = 0, 1, 2
    state = {node: UNSEEN for node in graph}
    finished: list[str] = []

    def visit(node: str) -> None:
        if state[node] == ON_PATH:
            raise ValueError(f"cycle through {node!r}: no topological order exists")
        if state[node] == EXPLORED:
            return

        state[node] = ON_PATH
        for neighbour in graph[node]:
            visit(neighbour)
        state[node] = EXPLORED
        # Everything reachable from `node` is already in `finished`, so once
        # the list is reversed `node` will sit in front of all of it.
        finished.append(node)

    for node in graph:
        visit(node)

    finished.reverse()
    return finished


print(" -> ".join(topological_sort_dfs(build_graph)))

assets -> config -> utils -> ui -> api -> app -> tests

A different answer, and just as valid — check the eight rules against it. The recursion that produced it starts at config and dives straight to the bottom of the graph:

tests has nowhere to go, so it finishes first and is appended first, then app, then api. Back in utils, the second neighbour ui is explored, finds app already fully explored, and finishes; then utils, then config. The outer loop moves on to assets, whose only neighbour is explored, so it finishes last. The finish list is tests, app, api, ui, utils, config, assets — reverse it for the printed answer.

Two states would not be enough. "Seen" and "not seen" cannot tell the difference between a node you are still inside (a cycle) and a node you finished exploring ten calls ago (a perfectly legal shortcut, like config reaching api twice by two different routes). That is what the third state buys.

The order is generally not unique

Both algorithms are correct and they disagree, which is the expected state of affairs. Any node with in-degree 0 is a legal next pick, so whenever two or more are ready at once, every choice leads to a valid order. The order is unique only when the ready pool holds exactly one node at every step — that is, when the graph contains a directed path passing through every node, a Hamiltonian path.

Sometimes you want a specific one of the valid orders, and the usual request is the alphabetically smallest. Swap the queue for a min-heap and always take the smallest ready node instead of the oldest. This is Kahn's algorithm with three lines changed:

import heapq


def topological_sort_smallest(graph: dict[str, list[str]]) -> list[str]:
    """The alphabetically smallest topological order of `graph`.

    Identical to Kahn's algorithm except that the ready set is a min-heap, so
    the smallest currently-available node is always taken next.
    """
    in_degree = {node: 0 for node in graph}
    for node, neighbours in graph.items():
        for neighbour in neighbours:
            in_degree[neighbour] += 1

    ready = [node for node in graph if in_degree[node] == 0]
    heapq.heapify(ready)
    order: list[str] = []

    while ready:
        node = heapq.heappop(ready)
        order.append(node)
        for neighbour in graph[node]:
            in_degree[neighbour] -= 1
            if in_degree[neighbour] == 0:
                heapq.heappush(ready, neighbour)

    if len(order) != len(graph):
        raise ValueError("the graph has a cycle, so no topological order exists")
    return order


print(" -> ".join(topological_sort_smallest(build_graph)))

assets -> config -> utils -> api -> ui -> app -> tests

assets now comes out before config because a sorts before c, and the free choice between api and ui resolves to api. The heap makes every pick O(log V) instead of O(1), so the total becomes O(V log V + E) — a real but usually irrelevant cost, and the price of a reproducible, human-friendly ordering.

Being greedy at every step really does give the globally smallest order: the first position takes the smallest node that may legally go first, the second takes the smallest that may legally follow it, and so on. That is smallest in the list-comparison sense, one position at a time — not "the order with the fewest total moves" or any other objective.

How the code maps to the idea

The in-degree count is the "waiting on" column of the table above, built in one sweep. The outer loop touches every node and the inner loop touches every edge, and no edge is counted twice because each edge is stored exactly once, in the adjacency list of its source.

The ready deque is the pool of runnable work. It is seeded with the in-degree-0 nodes, and it can only ever gain a node whose count has just reached 0.

The while ready loop is the "take, output, delete" step. Deleting a node is never done literally — nothing is removed from the dictionary. Decrementing the neighbours' counts has exactly the same effect and costs nothing.

The final length check is the cycle detector, covered in a moment.

Here is the same algorithm with the queue printed at every step, so you can compare it against the hand trace line by line:

def topological_sort_traced(graph: dict[str, list[str]]) -> list[str]:
    """Kahn's algorithm, printing the ready queue after every step."""
    in_degree = {node: 0 for node in graph}
    for node, neighbours in graph.items():
        for neighbour in neighbours:
            in_degree[neighbour] += 1

    ready = deque(node for node in graph if in_degree[node] == 0)
    order: list[str] = []
    print(f"start        ready={list(ready)}")

    while ready:
        node = ready.popleft()
        order.append(node)
        freed = []
        for neighbour in graph[node]:
            in_degree[neighbour] -= 1
            if in_degree[neighbour] == 0:
                ready.append(neighbour)
                freed.append(neighbour)
        print(f"take {node:<7} ready={str(list(ready)):<22} freed={freed}")

    return order


topological_sort_traced(build_graph)

start        ready=['config', 'assets']
take config  ready=['assets', 'utils']    freed=['utils']
take assets  ready=['utils']              freed=[]
take utils   ready=['api', 'ui']          freed=['api', 'ui']
take api     ready=['ui']                 freed=[]
take ui      ready=['app']                freed=['app']
take app     ready=['tests']              freed=['tests']
take tests   ready=[]                     freed=[]

The correctness argument falls out of this. A node is appended to order only when its in-degree has hit 0. Its in-degree started at the number of arrows pointing at it, and the only thing that ever decrements it is the emission of the node at the other end of one of those arrows. So by the time a node is emitted, every one of its predecessors has already been emitted — which is precisely the definition of a topological order.

Edge cases need no special handling. An empty graph produces an empty queue and an empty order, and 0 != 0 is false, so nothing is raised. A graph with no edges at all leaves every in-degree at 0, so every node is ready immediately and comes out in insertion order. A single node with a self-loop has in-degree 1, is never ready, and is correctly reported as a cycle — because a self-loop is a cycle.

The one input that will bite you is a graph where some node appears only as a neighbour and never as a key. in_degree[neighbour] += 1 then raises KeyError. Normalise first, or build the node set from both sides.

Cycle detection comes for free

Add one arrow to the build graph — say app now generates a helper that utils imports — and the whole thing becomes unorderable. Rather than raise, this version reports what it managed to place and what it did not:

def topological_sort_report(graph: dict[str, list[str]]) -> tuple[list[str], list[str]]:
    """Kahn's algorithm that reports what it could not place instead of raising."""
    in_degree = {node: 0 for node in graph}
    for node, neighbours in graph.items():
        for neighbour in neighbours:
            in_degree[neighbour] += 1

    ready = deque(node for node in graph if in_degree[node] == 0)
    order: list[str] = []

    while ready:
        node = ready.popleft()
        order.append(node)
        for neighbour in graph[node]:
            in_degree[neighbour] -= 1
            if in_degree[neighbour] == 0:
                ready.append(neighbour)

    placed = set(order)
    return order, sorted(node for node in graph if node not in placed)


cyclic_graph = {node: list(edges) for node, edges in build_graph.items()}
cyclic_graph["app"].append("utils")  # the app now feeds a helper back into utils

placed, stuck = topological_sort_report(cyclic_graph)
print(f"placed {len(placed)} of {len(cyclic_graph)}: {placed}")
print(f"stuck: {stuck}")

try:
    topological_sort_dfs(cyclic_graph)
except ValueError as error:
    print(f"dfs: {error}")

placed 2 of 7: ['config', 'assets']
stuck: ['api', 'app', 'tests', 'ui', 'utils']
dfs: cycle through 'utils': no topological order exists

Only config and assets come out. Now the argument for why a short output means a cycle, in both directions, because this is the part people take on faith and should not.

If there is a cycle, the output must be short. Take any node on the cycle. Its in-degree includes the arrow from its predecessor on that cycle, so it can only reach 0 after that predecessor is emitted. Follow that reasoning around the loop and each cycle node needs another cycle node emitted first. There is no first one, so none of them is ever emitted, and the count comes up short.

If the output is short, there must be a cycle. Suppose the loop ended with some nodes left over. Every leftover node has in-degree greater than 0 — otherwise it would have been queued and taken. All the decrements from emitted nodes have already happened, so that remaining count must come from an arrow whose source is also a leftover node. So from any leftover node you can step backwards to another leftover node, and from there backwards again, forever. The leftover set is finite, so you must eventually revisit a node, and that repeated backwards walk is a cycle.

Together those two statements make len(order) != len(graph) an exact test: short output if and only if cycle. No extra pass, no extra memory.

Both implementations detect it, and they tell you different things. Kahn's hands you the full set of nodes involved — here all five. That set mixes two kinds of node. One new arrow closes two cycles, utils -> api -> app -> utils and utils -> ui -> app -> utils, so four of the five (utils, api, ui and app) genuinely sit on a cycle. Only tests is merely downstream: it is on no cycle at all, and is blocked forever by one it is not part of. The depth-first version names a single node on a cycle itself, which is more useful for an error message and less useful for a report. Real tools often want both.

What the standard library already gives you

Python 3.9 added graphlib.TopologicalSorter, so for straightforward cases you do not need to write any of this. It takes the arrows the other way round — each key maps to the things that must come before it — and it raises graphlib.CycleError on a cycle.

from graphlib import TopologicalSorter

# graphlib wants the arrows the other way round: each key maps to the nodes
# that must come before it.
dependencies: dict[str, list[str]] = {node: [] for node in build_graph}
for node, neighbours in build_graph.items():
    for neighbour in neighbours:
        dependencies[neighbour].append(node)

print(" -> ".join(TopologicalSorter(dependencies).static_order()))

config -> assets -> utils -> api -> ui -> app -> tests

static_order() is the one-shot version. The class also has a prepare / get_ready / done interface that hands you every currently-runnable node at once, which is what you want when the tasks are being executed in parallel — the whole batch can go out to a worker pool together.

Complexity

Time: O(V + E), for both implementations. V is the number of nodes, E the number of edges, and both terms are needed because a graph can have many nodes and few edges or the reverse.

For Kahn's, count it in three parts. Building the in-degree map visits every node once and every edge once: V + E. Seeding the queue scans every node once: V. In the main loop, each node is appended to the queue exactly once — its in-degree starts positive or zero, only ever decreases, and triggers a single append when it touches 0 — so there are exactly V pops, each O(1) on a deque. Each pop scans that node's outgoing edges, and since every node is popped once, every edge is scanned exactly once across the whole run: E. Add them up: (V + E) + V + V + E, which is 3V + 2E, which is O(V + E).

The depth-first version counts the same way. visit is called once from the outer loop for every node and once for every edge, so V + E calls in total. Only the first call on a given node gets past the state check and does work, and that work is iterating the node's outgoing edges — E of them across the whole graph.

There is no best or worst case worth naming: on a DAG both algorithms touch every node and every edge whatever its shape, so all three cases are O(V + E). Detecting a cycle is not slower than succeeding — Kahn's is in fact faster on a cyclic graph, because it stops early with work left undone.

With a heap: O(V log V + E). The edge work is unchanged. What changes is that each of the V pushes and V pops costs O(log k) where k is the current heap size, and k never exceeds V.

Space: O(V). The in-degree dictionary holds one entry per node, the ready queue holds at most V nodes, and the output list holds exactly V. The edges are not copied. The depth-first version replaces the queue with Python's call stack, which is the same O(V) in the worst case — but it is the call stack, and Python's default recursion limit is 1000. A dependency chain 5,000 modules deep will raise RecursionError in the recursive version and be perfectly fine in Kahn's.

One representation warning: all of this assumes an adjacency list, where scanning a node's neighbours costs one step per actual edge. With an adjacency matrix, finding a node's neighbours means scanning a whole row of V entries, so the total becomes O(V²) no matter how sparse the graph is.

When to use it, and when not to

Use it whenever you have things to do and rules about which must come first. That is the entire signature of the problem. If you find yourself hand-sorting a list of steps, or worse, "just running it twice until it settles", you want a topological sort.

Use Kahn's algorithm by default. It is iterative, so it cannot blow the stack; it gives you the complete set of nodes involved in a failure; and its ready pool is a natural fit for parallel execution — every node in the pool can be started at the same time.

Use the depth-first version when you are already doing a depth-first traversal for other reasons, when you want a single named node on the cycle for an error message, or when you want the shortest possible implementation and you know the graph is shallow.

Do not use it on an undirected graph. "Before" needs a direction; an undirected edge does not have one. And do not use it on a graph you have not verified is acyclic — check the output length rather than assuming.

Do not reach for it when the order is determined by a key rather than by constraints. If the rule is "earliest deadline first" or "highest priority first", you want an ordinary sort or a priority queue, not a graph. Topological sort answers "what is legal", not "what is best".

One extension is worth knowing because it comes up constantly: once nodes are in topological order, you can process them in that order and be certain every predecessor is already done. That turns shortest paths on a DAG into a single O(V + E) sweep with no priority queue at all — faster than Dijkstra's algorithm, and it works with negative edge weights, which Dijkstra's cannot. Flip the comparison and the same sweep gives you the longest path, which is how project-management tools compute the critical path of a schedule.

Where it shows up in the real world

Build systems. This is the canonical use. make reads target-to-prerequisite rules and builds in dependency order; Ninja, Bazel and Gradle do the same over much larger action graphs. Cycles are always called out: Bazel and Ninja refuse to build at all, and GNU make prints Circular a <- b dependency dropped and continues without the offending edge.

Package managers. dpkg configures newly unpacked Debian packages in an order that respects their Depends fields. Cargo compiles a crate's dependency graph bottom-up, so nothing is ever compiled before something it uses.

Spreadsheet recalculation. When a cell changes, Excel and Google Sheets recompute the cells that depend on it, and those cells' dependents, in topological order. It is also where end users meet cycle detection most often: the "circular reference" warning is exactly the failure described above.

Task schedulers. Apache Airflow names the concept in its core object — a workflow is a DAG, tasks are nodes, dependencies are edges, and the scheduler runs whatever is currently ready. Adding a cycle makes the DAG fail to load rather than deadlock at runtime.

Service startup. systemd orders units from their After= and Before= declarations. When the constraints are contradictory it logs Found ordering cycle and deletes one job to break it, rather than hanging forever.

Course prerequisites. Working out a legal sequence of courses for a degree is the textbook version of this problem, and university planning tools really do solve it this way.

Common mistakes

Reversing the edge direction. An edge from utils to api can mean "utils comes first" or "utils depends on api" depending on who wrote the data, and the two produce exactly reversed answers. Both are topological orders of some graph, so nothing crashes — you just build everything backwards. Write down what an arrow means before you write the loop, and note that graphlib uses the opposite convention to the code here.

Forgetting to reverse the DFS result. Without the final reverse(), you get a valid topological order of the graph with all its arrows flipped. Same silent failure.

Using two states instead of three in the DFS. A plain visited set cannot tell a node on the current path apart from one fully explored ten calls ago, so it either misses cycles or reports one wherever two paths meet.

Nodes missing from the graph dictionary. A sink node such as tests has no outgoing edges but still needs a key mapping to an empty list, or the in-degree pass raises KeyError on it.

Assuming the answer is unique. A test that asserts one exact list will pass on your machine and fail when someone changes the insertion order of the input dictionary. Assert the property instead: every edge points forwards, and the output holds every node exactly once.

Using list.pop(0) instead of a deque. That is O(n) per removal, which turns an O(V + E) algorithm into O(V² + E).

Practice

1. Write a checker that takes a graph and a candidate order and returns True only if every edge points forwards and every node appears exactly once.
2. Modify Kahn's algorithm to return the levels of the graph: all in-degree-0 nodes as level 0, everything freed by them as level 1, and so on. Each level is a batch that could run in parallel.
3. Return the largest alphabetical order rather than the smallest, using the same heap trick.
4. Recover the actual cycle, not just its existence: when the depth-first search meets a node that is on the current path, print the sequence of nodes from that node round to itself.
5. Rewrite the depth-first version iteratively with an explicit stack, so it survives a chain of 100,000 nodes, and confirm the recursive one raises RecursionError on the same input.

Summary

Topological sort turns a dependency graph into a runnable list, in time linear in the size of the graph. Kahn's algorithm is the one to reach for: a queue, an in-degree count, and a length check at the end that detects cycles at no extra cost. Remember that the answer is usually one of many valid answers — if you need a specific one, choose it deliberately with a heap rather than depending on whatever your dictionary's insertion order happened to be.

Keep reading

• Graphs in Python — adjacency lists and matrices, and why the choice changes the complexity above.
• Depth-First Search — the traversal the second implementation is built on, in full.
• Breadth-First Search — the other queue-driven graph algorithm, and how it differs from Kahn's.
• Heaps and Priority Queues — what heapq is doing when you ask for the smallest order.
• Dijkstra's Algorithm — shortest paths on a general weighted graph, and why a DAG lets you skip its priority queue.