Topological SortTopological sort

01Why it exists

Reach for it when you see:Dependencies, ordering, prerequisites, A must finish before B, build or install order, DAGs, whether a schedule can complete, whether there is a circular dependency.

02The core idea

A topological order of a directed graph lines every node up so that for each edge u → v, u comes before v. One exists exactly when the graph is a DAG (directed acyclic graph), and there is usually more than one. Kahn's algorithm works from the obvious angle — whoever is not waiting goes first: a node with in-degree 0 has no prerequisites, so it can be placed immediately; remove its outgoing edges and some other nodes drop to in-degree 0, and it is their turn. The DFS approach comes at it from the other end: a node is not finished until everything reachable from it is finished, so reversing the finish order gives a topological order.

Why it is correct: Kahn only queues v once indeg[v] reaches 0, and by then every edge u → v pointing at it has been removed, which means every such u has already been emitted — so every edge is respected. It never gets stuck on a DAG, because a non-empty DAG always has a node of in-degree 0. If it did not, you could keep walking backwards along incoming edges, and with finitely many nodes you would eventually revisit one and close a cycle; and removing a node leaves a DAG behind. Conversely, if the queue empties with nodes still unemitted, every remaining node has in-degree ≥ 1, so walking backwards must loop — which is why emitting fewer than V nodes means there is a cycle, the cycle detection Kahn gives you for free. For the DFS version, take any edge u → v: when it is examined, a white v finishes recursively before u, a black v finished long ago, and a grey v (still on the call stack) is a cycle. So with no cycles v always finishes before u, and after reversal u sits before v.

Complexity: Kahn scans every edge once to build the in-degree table, O(E); each node enters and leaves the queue once, O(V); and each edge decrements an in-degree exactly once, when its source is dequeued, O(E) — O(V+E) in total. The DFS version enters each node once and examines each edge once, also O(V+E). Neither has a best or worst case worth distinguishing: the whole graph has to be traversed either way. The extra space is the in-degree table, the queue, the colour array and the output, all O(V) (the adjacency list's own O(V+E) counts as input). DFS recursion can go V deep in the worst case, on one long chain, and Python's default recursion limit is only 1000, so use Kahn when there are many nodes.

The most common mistake is pointing the edges the wrong way: in LeetCode 207 and 210, [a, b] means "b must be taken before a", so the edge is b → a. With the DFS version people forget to reverse the finish order, or use a single visited boolean with no separate grey state, which happily emits a bogus order even when the graph has a cycle. The outer loop also has to try every node, since the graph need not be connected. How this relates to the neighbouring lessons: Kahn's queue loop is the skeleton of BFS, the DFS version is DFS post-order, and the three-colour marking is identical to Cycle Detection — topological sort is really "cycle detection that records the order on the way". For the lexicographically smallest order, swap the queue for a min-heap and the time becomes O(V log V + E); to find the fewest parallel rounds, have Kahn process a whole layer at a time. And once you have a topological order, relaxing the edges in that order gives shortest paths on a DAG, which is what DAG Shortest Path does.

03The algorithm

1. 1Turn each dependency into an edge: "u must come before v" means adding u → v and indeg[v] += 1. Work out which direction the problem's pairs point in before you write anything.
2. 2Put every node with in-degree 0 into the queue — those have no prerequisites at all.
3. 3Take u off the queue and append it to the answer; for each outgoing edge u → v, do indeg[v] -= 1, and push v when it reaches 0.
4. 4Stop when the queue is empty. If the answer has V nodes it is a topological order; fewer than V means a cycle, and every node whose in-degree is still above 0 is either on the cycle or downstream of it.
5. 5The DFS version: three-colour marking, with the outer loop calling dfs on every white node. A grey neighbour means a cycle. A node is appended to post only once all of its neighbours are done, and the answer is post reversed.
6. 6Variations: to process in parallel batches, drain a whole layer at once before computing the next, and the number of layers is the minimum number of rounds; for the lexicographically smallest order, swap the queue for a min-heap.

04Interactive demo

Six front-end packages and eight dependencies, where an arrow u → v means u has to be installed before v. In "Kahn · in-degree" mode, watch the in= under each node: every removed edge (it turns dashed) drops it by one, a package that hits 0 turns yellow and enters the queue, blue is the one being processed, and filled nodes are already emitted. In "DFS · finish order" mode, yellow marks the packages still on the call stack, the number under each node is the position in which it finished, and the right-hand column lists both the finish order and its reverse. Compare the two results: Kahn gives react → ts → r-dom → lint → next → app and DFS gives ts → lint → react → r-dom → next → app. The orders differ, but both respect every dependency.

05Code

Both languages implement Kahn and DFS. The example graph is the one from the interactive demo, and the printed output matches what each mode produces. Kahn needs no recursion and detects cycles for free, which makes it the usual default in practice; the DFS version shares its three-colour marking with cycle detection, so it fits naturally where you are already running a DFS. Python adds a layered version whose layers can each run in parallel, and C++ adds a variant that swaps the queue for a min-heap to get the lexicographically smallest order.

from collections import deque


def topo_kahn(n, edges):
    """Kahn: repeatedly take a node with in-degree 0. Returns [] if there is a cycle. O(V+E)"""
    adj = [[] for _ in range(n)]
    indeg = [0] * n
    for u, v in edges:                  # u → v: u must come before v
        adj[u].append(v)
        indeg[v] += 1
    queue = deque(i for i in range(n) if indeg[i] == 0)
    order = []
    while queue:
        u = queue.popleft()
        order.append(u)
        for v in adj[u]:
            indeg[v] -= 1               # remove the edge u → v
            if indeg[v] == 0:           # every prerequisite of v is placed
                queue.append(v)
    return order if len(order) == n else []   # fewer than n means a cycle


def topo_dfs(n, edges):
    """DFS: three-colour marking, finish order reversed. O(V+E)"""
    adj = [[] for _ in range(n)]
    for u, v in edges:
        adj[u].append(v)
    WHITE, GRAY, BLACK = 0, 1, 2
    color = [WHITE] * n
    post = []

    def dfs(u):
        color[u] = GRAY                 # on the call stack
        for v in adj[u]:
            if color[v] == GRAY:        # back edge: there is a cycle
                return False
            if color[v] == WHITE and not dfs(v):
                return False
        color[u] = BLACK
        post.append(u)                  # u finishes only after everything it reaches
        return True

    for i in range(n):                  # the graph may be disconnected, so try every start
        if color[i] == WHITE and not dfs(i):
            return []
    return post[::-1]


def topo_layers(n, edges):
    """Kahn by layers: nodes in one layer are independent and can run in parallel"""
    adj = [[] for _ in range(n)]
    indeg = [0] * n
    for u, v in edges:
        adj[u].append(v)
        indeg[v] += 1
    layer = [i for i in range(n) if indeg[i] == 0]
    layers, count = [], 0
    while layer:
        layers.append(layer)
        count += len(layer)
        nxt = []
        for u in layer:                 # drain a whole layer, then compute the next one
            for v in adj[u]:
                indeg[v] -= 1
                if indeg[v] == 0:
                    nxt.append(v)
        layer = nxt
    return layers if count == n else []


if __name__ == "__main__":
    # Same graph as the interactive demo: 0 react, 1 ts, 2 r-dom, 3 lint, 4 next, 5 app
    edges = [(0, 2), (0, 4), (2, 4), (2, 5), (1, 3), (1, 4), (4, 5), (3, 5)]
    print(topo_kahn(6, edges))                    # [0, 1, 2, 3, 4, 5]
    print(topo_dfs(6, edges))                     # [1, 3, 0, 2, 4, 5]
    print(topo_layers(6, edges))                  # [[0, 1], [2, 3], [4], [5]]
    print(topo_kahn(3, [(0, 1), (1, 2), (2, 0)])) # [] (cycle)

06Practice

• LeetCode 1557Minimum Number of Vertices to Reach All Nodes (the nodes with in-degree 0)Medium
• LeetCode 210Course Schedule II (mind the direction of the edges)Medium
• LeetCode 2115Find All Possible Recipes from Given Supplies (Kahn over string nodes)Medium
• LeetCode 802Find Eventual Safe States (Kahn on the reversed graph, or three-colour DFS)Medium
• LeetCode 2050Parallel Courses III (earliest finish time along a topological order)Hard
• LeetCode 1203Sort Items by Groups Respecting Dependencies (two levels of topological sort)Hard