Graphs and topological sort

A graph is a set of nodes and the edges between them. Many real problems are graphs: services that call each other, packages that depend on packages, tasks that must run in order. The question you most often ask about a dependency graph is: in what order can I do these things, so that every task runs after its prerequisites?

That question is answered by a topological sort. It exists only when the graph has no cycles. A cycle means "A waits for B, which waits for A", and no order can satisfy it.

The big idea

Store the graph as adjacency lists: for each node, a list of the nodes it points to. This takes space proportional to nodes plus edges, and it's the standard representation for sparse graphs. An adjacency matrix would need n² cells, which wastes space when most pairs have no edge.

Kahn's algorithm sorts the graph using in-degrees, the number of prerequisites each node still has. Start with the nodes that have none. Output one, remove its edges, and any node whose prerequisites are now all done becomes ready. Repeat until nothing is left.

Walking through it

Here is a build order for packages, where each package lists what it needs first:

from collections import deque

def topo_sort(deps):                             # node -> prerequisites
    pending = {n: set(d) for n, d in deps.items()}
    ready = deque(sorted(n for n, d in pending.items() if not d))
    order = []
    while ready:
        n = ready.popleft(); order.append(n)
        for m, d in pending.items():
            if n in d:
                d.remove(n)
                if not d and m not in order and m not in ready:
                    ready.append(m)
    return order

print(topo_sort({"app": ["lib", "proto"], "lib": ["proto"], "proto": [], "test": ["app"]}))

Output:

['proto', 'lib', 'app', 'test']

proto has no prerequisites, so it goes first. Once it's done, lib is ready, then app, which needs both lib and proto. Finally test, which needs app. This sketch scans all nodes on each step, so it's O(n²) for clarity. Keep a count of prerequisites per node for an O(V + E) version.

The output is one valid order, not the only one. Several orders can satisfy the same graph, so the result depends on the order you pick ready nodes.

Detecting cycles

If Kahn's algorithm finishes with fewer nodes output than the graph has, the leftover nodes are in a cycle, or depend on one. The error should name those nodes, because the fix is to break the cycle, not to retry. Build tools, package managers and migration runners all report cycles this way.

Where this shows up

• Build systems such as make and Bazel run targets in topological order.
• Package managers install dependencies before the packages that need them.
• Database migrations or schema changes that depend on each other.
• Version control. Git's commit history is a directed acyclic graph, covered in Git internals.

Common mistakes

• Running tasks in list order and assuming it's a valid build order.
• Forgetting to check for a cycle, so the sort silently returns a partial order.
• Using an adjacency matrix for a large sparse graph, which takes n² memory.

Check yourself

• Why does a cycle make a topological order impossible? Answer: each node in the cycle must come before the next, so the first one has no node that can start the chain.
• Why does Kahn's algorithm reveal a cycle at the end? Answer: nodes in a cycle never reach zero prerequisites, so they're never output, and the output comes up short.

Key takeaways

• Store graphs as adjacency lists for sparse data.
• Kahn's algorithm orders nodes by repeatedly taking those with zero prerequisites.
• If the output is short, the graph has a cycle, and no valid order exists.

Further learning

Next, return to the data structures overview to pick the right structure for your next problem.