Topological Sort Explained, with Code

Mohammed Islam Hadjoudj

Expert Operations Research Engineer

What Is a Topological Sort?

A topological sort is a linear ordering of the nodes of a directed acyclic graph (DAG) such that, for every directed edge from u to v, node u appears before node v. In plain terms: line everything up so every arrow points forward.

Two conditions are baked into that definition. The graph must be directed (dependencies have a direction: A before B is not the same as B before A) and acyclic (no cycles). If A must come before B and B must come before A, no valid order can exist. Trees and DAGs are close cousins here; for the tree side, see rooted trees.

When You Need It

Topological sort is the answer whenever a problem sounds like "do these things in an order that respects their prerequisites." You will recognize it by these signals:

• Dependencies: "Task X requires task Y to be finished first."
• Ordering or scheduling: "In what order can I take these courses?"
• Build and compile: "Compile modules so every import already exists."
• Resolution: "Install packages so each dependency is installed before the thing that needs it."

It is one of the most common patterns in technical interviews, which is why it appears in the guide to graph algorithms for coding interviews and forms a stage of the graph theory study roadmap.

Kahn's Algorithm, Step by Step

The most intuitive method is Kahn's algorithm. It leans on one number per node: the in-degree, the count of incoming edges. A node with in-degree 0 has no unmet prerequisites, so it is safe to place next.

The loop is simple: take any node with in-degree 0, output it, and remove its outgoing edges, which lowers its neighbours' in-degrees. Repeat until nothing is left. Let's run it on this DAG. Each node is badged with its position in one valid order.

Here is the trace. The queue holds nodes whose in-degree has hit 0. We start with A, the only node that depends on nothing.

Notice that after taking A, both B and C had their in-degree drop to 0 at once. Either could go next, which is exactly why a DAG usually has many valid orders. Watching the in-degrees fall on a live graph makes it click, which you can try in the algorithm visualizer.

Implementation in Python

Kahn's algorithm translates almost directly into code. We compute every in-degree, seed a queue with the zero-in-degree nodes, and drain it.

from collections import deque, defaultdict

def topological_sort(num_nodes, edges):
    graph = defaultdict(list)
    in_degree = [0] * num_nodes

    for u, v in edges:          # edge u -> v means u before v
        graph[u].append(v)
        in_degree[v] += 1

    # Seed with every node that has no prerequisites.
    queue = deque(n for n in range(num_nodes) if in_degree[n] == 0)
    order = []

    while queue:
        node = queue.popleft()
        order.append(node)
        for neighbour in graph[node]:
            in_degree[neighbour] -= 1        # remove the edge
            if in_degree[neighbour] == 0:    # no prerequisites left
                queue.append(neighbour)

    # If some node never reached in-degree 0, a cycle blocked it.
    if len(order) == num_nodes:
        return order
    return []   # cycle detected, no valid ordering

The final check is the elegant part: if the output is missing any node, those nodes are trapped in a cycle. So the same code that orders a DAG also detects whether the graph was a DAG at all.

The DFS Approach

There is a second classic method built on depth-first search. Run DFS, and when a node finishes (all its descendants are explored), push it onto a stack. The topological order is the stack read in reverse.

The intuition: a node finishes only after everything it points to has finished, so in reverse-finish order it lands before all its descendants. The DFS version needs no in-degree bookkeeping, but you must still guard against cycles by tracking nodes on the current recursion path. Both approaches are equally valid; Kahn's tends to be easier to reason about, while DFS is more compact.

Cycles and Why They Break It

A topological order exists if and only if the graph is acyclic. The reason is immediate: a cycle A → B → A demands that A comes before B and B comes before A at the same time, which is impossible in a line.

The useful consequence: topological sort is also a cycle detector. In Kahn's algorithm, if you cannot output all V nodes, the leftover nodes form at least one cycle. In the DFS version, meeting a node already on your current path signals a cycle.

This is why "Course Schedule" style interview questions, which really ask "is this even possible?", are solved with a topological sort.

Complexity

Both algorithms are optimal: they touch every node and every edge exactly once.

That linear cost is why topological sort scales to huge dependency graphs. For how it stacks up against every other graph algorithm, see the complexity guide and the one-page cheat sheet.

Real-World Applications

• Build systems: Make, Bazel, and friends topologically sort targets so dependencies build first.
• Package managers: npm, pip, and apt resolve install order from a dependency DAG.
• Task and job scheduling: spreadsheets recalculating cells, CI pipelines ordering stages, course planners.
• Compilers: ordering declarations and evaluating expressions so every symbol is defined before use.