Topological Sort

Updated Nov 19, 2026 · 4 min read
On this page

    Some problems are about order under constraints: course B needs course A, package X needs package Y, letter t comes before f in an alien alphabet. Draw an arrow from "must happen first" to "happens after", and you have a directed graph. A topological order lists the nodes so that every arrow points forward. It exists exactly when the graph has no cycle, so the same algorithm answers "can all courses be finished?"

    When to recognise it

    • Prerequisites, dependencies, build order, "must come before".
    • "Is it possible to finish / schedule all of them?": that means "is there a cycle?"
    • "Return any valid order": the order itself.
    • An ordering rule hidden in data: alien dictionary (compare neighbouring words), sequence reconstruction.
    • "Minimum number of semesters / rounds": process Kahn's algorithm level by level and count the rounds.

    How Kahn's algorithm works

    Count, for every node, how many arrows point into it: its indegree, the number of things it still waits for. Start with every node whose indegree is 0. Each time you take one, remove its outgoing arrows; any node whose indegree drops to 0 is ready too.

    Five topics: intro before arrays and hashing, arrays and hashing before graphs, hashing before DP. Indegrees start at intro 0, arrays 1, hashing 1, graphs 2, DP 1. Taking intro frees arrays and hashin
    Five topics: intro before arrays and hashing, arrays and hashing before graphs, hashing before DP. Indegrees start at intro 0, arrays 1, hashing 1, graphs 2, DP 1. Taking intro frees arrays and hashing; taking hashing frees graphs and DP. Order: intro, arrays, hashing, graphs, DP.

    Template

    from collections import deque, defaultdict
    
    def topo_order(n, edges):
        """Kahn's algorithm. edges are (before, after). Returns [] if there is a cycle."""
        graph = defaultdict(list)
        indegree = [0] * n
        for a, b in edges:
            graph[a].append(b)
            indegree[b] += 1
        q = deque(i for i in range(n) if indegree[i] == 0)   # nothing left to wait for
        order = []
        while q:
            node = q.popleft()
            order.append(node)
            for nxt in graph[node]:
                indegree[nxt] -= 1
                if indegree[nxt] == 0:
                    q.append(nxt)
        return order if len(order) == n else []     # leftovers sit on a cycle

    Time O(V + E), space O(V + E). If some nodes never reach indegree 0, they are waiting on each other in a cycle, so the order is shorter than n, and the answer to "can you finish?" is no.

    The DFS version

    DFS gives the same result: a node is finished once all of its dependents are finished, so reversing the finishing order gives a topological order. Cycle detection needs three states, because a node you are still exploring (grey) is different from one you already finished (black).

    from collections import defaultdict
    
    def topo_dfs(n, edges):
        """DFS version: post-order, reversed. Three colours detect a cycle (grey = on the current path)."""
        graph = defaultdict(list)
        for a, b in edges:
            graph[a].append(b)
        WHITE, GREY, BLACK = 0, 1, 2
        color = [WHITE] * n
        out = []
        def visit(u):
            color[u] = GREY
            for v in graph[u]:
                if color[v] == GREY:
                    return False                  # back edge: cycle
                if color[v] == WHITE and not visit(v):
                    return False
            color[u] = BLACK
            out.append(u)                         # all of u's dependents are done
            return True
        for u in range(n):
            if color[u] == WHITE and not visit(u):
                return []
        return out[::-1]

    Kahn's version is usually easier to get right under pressure, avoids recursion limits, and its level-by-level form answers "minimum number of semesters". Know that the DFS version exists and why it needs three colours.

    Getting the edges right

    The pair [course, prereq] = [1, 0] becomes the edge 0 → 1, from prerequisite to course. Indegree counts how many things a node waits for; flipping the edges reverses the order.
    The pair [course, prereq] = [1, 0] becomes the edge 0 → 1, from prerequisite to course. Indegree counts how many things a node waits for; flipping the edges reverses the order.

    Most wrong answers come from building the graph backwards. Write one line on the whiteboard: "edge = prereq → course", and build from it.

    Common bugs

    • Reversed edges, from reading [a, b] the wrong way round.
    • Missing isolated nodes: nodes with no edges must still be in the output. Loop over range(n), not just the keys of the graph.
    • Two-state DFS cycle check: marking nodes only "visited" treats a node reached from two branches (a diamond) as a cycle. Use grey and black.
    • Alien dictionary edge cases: compare only the first different letter of neighbouring words, and if a longer word comes before its own prefix ("abc" before "ab"), there is no valid order.
    • Assuming the order is unique. Any valid order is accepted unless the question says otherwise. If it asks whether exactly one order exists, check that the queue never holds more than one node.

    Say this in the interview

    • "I build an indegree count. Anything at zero has no unmet prerequisites, so it can go next. If I can't output all n nodes, the rest form a cycle."
    • "Each node and edge is handled once: O(V + E)."

    Problems for this pattern

    1. Course Schedule: cycle check with Kahn's algorithm.
    2. Course Schedule II: return the order.
    3. Minimum Height Trees: peel leaves layer by layer, Kahn-style.
    4. Alien Dictionary: build the edges from neighbouring words.
    5. Longest Increasing Path in a Matrix: edges point to bigger neighbours; count Kahn layers (or DFS with a cache).

    Related

    Graphs · Graph BFS and DFS · Union-Find (cycles in undirected graphs) · Pattern Recognition Cheat Sheet