Topological sort — ordering nodes so every dependency comes first

Given a set of tasks where some must happen before others, topological sort produces a valid order that respects every dependency at once — and it only exists at all when the dependency graph has no cycle, which is the real, structural reason it's also a cycle-detection tool.

Intermediate

5 min read

The exact problem: a valid order respecting every "must come before" edge

Course prerequisites: "Calc 2" requires "Calc 1", "Linear Algebra" requires
"Calc 1", "Diff Eq" requires both "Calc 2" and "Linear Algebra"

A directed edge A → B means "A must come before B" — topological sort
produces ONE valid ordering satisfying every such edge simultaneously:
e.g. [Calc 1, Linear Algebra, Calc 2, Diff Eq] is valid;
     [Calc 1, Calc 2, Linear Algebra, Diff Eq] is ALSO valid — multiple
     correct answers can exist, as long as every edge points forward

A topological sort of a directed graph is a linear ordering of every node such that for every directed edge A → B, A appears somewhere before B in the ordering. This is exactly the shape of course prerequisites, build-system task dependencies, or package installation order (the graphs lesson's own example) — and critically, more than one valid ordering can exist for the same graph, since two independent tasks with no edge between them can appear in either relative order.

Why this only works on a DAG — a directed graph with no cycle

If A requires B, AND B requires A (directly or through a longer chain),
there is NO valid order at all — satisfying "A before B" and "B before A"
simultaneously is a genuine contradiction, not just a hard search problem

A cycle in the dependency graph means a genuine contradiction — task A depending (directly or transitively) on task B, which depends back on A, has no valid completion order at all. This is the structural reason topological sort is only defined for a DAG (Directed Acyclic Graph): the algorithm doesn't just fail to find an ordering when a cycle exists, an ordering genuinely doesn't exist, which is exactly why running (or attempting to run) topological sort is also the standard way to detect a cycle in a directed graph in the first place.

Kahn's algorithm: repeatedly removing nodes with no remaining dependencies

from collections import deque
 
def topological_sort(graph, num_nodes):
    in_degree = [0] * num_nodes
    for node in graph:
        for neighbor in graph[node]:
            in_degree[neighbor] += 1  # count how many edges point INTO each node
 
    queue = deque([n for n in range(num_nodes) if in_degree[n] == 0])  # start with NO dependencies
    order = []
 
    while queue:
        node = queue.popleft()
        order.append(node)
        for neighbor in graph[node]:
            in_degree[neighbor] -= 1              # this dependency is now satisfied
            if in_degree[neighbor] == 0:            # neighbor has NO remaining unsatisfied dependencies
                queue.append(neighbor)
 
    return order if len(order) == num_nodes else None  # fewer nodes processed than exist = a CYCLE was present

Kahn's algorithm tracks each node's in-degree (how many edges point into it — how many prerequisites it still has), starts with every node that has zero remaining prerequisites, and repeatedly removes one such node from the queue, decrementing its neighbors' in-degrees as if that dependency were now satisfied — a neighbor joins the queue the moment its own in-degree drops to zero. The order nodes are removed in is a valid topological order, by construction: a node is only ever added to order once everything that had to come before it already has.

The cycle-detection payoff: fewer nodes processed than exist means a cycle

# If order ends up SHORTER than num_nodes, some nodes never reached
# in-degree zero — every remaining node is stuck waiting on something
# in a cycle that never gets satisfied, since nothing in that cycle
# can ever reach in-degree zero on its own

If the algorithm finishes with fewer nodes in order than exist in the graph, the remaining, un-processed nodes are exactly the ones caught in a cycle (or dependent on one) — their in-degree never reaches zero, because at least one of their prerequisites is itself waiting on something that's waiting on them. This is the concrete, structural reason this same algorithm doubles as cycle detection: a successful full topological sort is the proof that no cycle exists, and an incomplete one directly identifies that a cycle does.

DFS-based topological sort: the alternative, using finish order

def topological_sort_dfs(graph, num_nodes):
    visited = set()
    order = []
 
    def dfs(node):
        visited.add(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                dfs(neighbor)
        order.append(node)  # append AFTER visiting every neighbor — this node "finishes" last
 
    for node in range(num_nodes):
        if node not in visited:
            dfs(node)
 
    return order[::-1]  # REVERSE — the last node to finish belongs FIRST in the topological order

This DFS-based approach (the graphs lesson's own forward-reference to this lesson) appends each node to order only after recursively finishing all of its neighbors — meaning a node with no remaining dependents to explore finishes (and gets appended) before anything that depends on it, so reversing the final list produces a valid topological order. Both this and Kahn's algorithm are correct, O(V + E) approaches; Kahn's is often preferred when cycle detection needs to be explicit and incremental (which nodes are stuck, specifically), while the DFS version is a natural fit when the traversal is already DFS-based for other reasons.