Topological sort

You’ll recognise it when

• The input is a list of “a must come before b” rules: prerequisites, dependencies, build steps, recipes that need other recipes.
• You’re asked for any valid order, or whether one exists at all (“can you finish all courses?”).
• Something must be processed only after everything it depends on: spreadsheet cells, package installs, DP over a directed graph.
• The question hints at a cycle being the reason an answer might not exist.

It’s easy to mistake for plain BFS, since Kahn’s algorithm also uses a queue. The difference is when a node goes in: BFS adds it the first time it’s seen, topological sort only once all of its incoming edges are gone.

The idea

Think of getting dressed. Socks before shoes, underwear before trousers, trousers before shoes, shirt before tie. You don’t need the whole plan up front: at any moment, put on something whose requirements are all already on you. Socks are free from the start. Shoes become free only once both socks and trousers are on.

That’s the whole algorithm. A topological order lists the nodes of a directed graph so that every edge u → v has u earlier than v. Keep, for each node, a count of how many of its prerequisites are still missing: its indegree. A node with indegree 0 is free to go next. Placing it deletes its outgoing edges, which may free more nodes.

A cycle makes an order impossible. If a → b → c → a, then a must come before c and c before a. Kahn’s algorithm finds this by itself: the nodes on a cycle wait on each other forever, so they never reach indegree 0 and never come out.

How it works

The input is n nodes numbered from 0 and a list of edges (u, v) meaning u before v. The graphic follows the steps as you scroll; the example is eight courses and their prerequisites.

Why it’s correct: a node joins the queue only when every edge into it has been removed, and an edge is removed only when its start node is placed. So every node comes after all of its prerequisites. And if the graph has no cycle, some unplaced node always has indegree 0 (follow incoming edges backwards among unplaced nodes: without a cycle you must hit a start), so nothing gets left behind.

Here the same code runs into a cycle. After 0 and 5 are placed, nodes 1, 2 and 3 each wait on another, and 4 waits on 3:

The order this code produces is fixed by two choices: sources start in increasing id, and each node’s edges are processed in input order. Many valid orders usually exist; this is one of them.

from collections import deque

def topo_sort(n, edges):
    """Kahn's algorithm. Each edge (u, v) means u must come before v.
    Returns an order of the nodes 0..n-1, or [] if there is a cycle."""
    adj = [[] for _ in range(n)]
    indegree = [0] * n
    for u, v in edges:
        adj[u].append(v)
        indegree[v] += 1

    queue = deque(v for v in range(n) if indegree[v] == 0)
    order = []
    while queue:
        u = queue.popleft()
        order.append(u)
        for v in adj[u]:              # "remove" the edge u -> v
            indegree[v] -= 1
            if indegree[v] == 0:
                queue.append(v)

    # Nodes left over never reached indegree 0: they sit on or after a cycle.
    if len(order) < n:
        return []
    return order

#include <queue>
#include <utility>
#include <vector>

// Kahn's algorithm. Each edge {u, v} means u must come before v.
// Returns an order of the nodes 0..n-1, or an empty vector if there is a cycle.
std::vector<int> topoSort(int n, const std::vector<std::pair<int, int>>& edges) {
    std::vector<std::vector<int>> adj(n);
    std::vector<int> indegree(n, 0);
    for (auto [u, v] : edges) {
        adj[u].push_back(v);
        indegree[v]++;
    }

    std::queue<int> queue;
    for (int v = 0; v < n; v++) {
        if (indegree[v] == 0) queue.push(v);
    }
    std::vector<int> order;
    while (!queue.empty()) {
        int u = queue.front();
        queue.pop();
        order.push_back(u);
        for (int v : adj[u]) {                           // "remove" the edge u -> v
            indegree[v]--;
            if (indegree[v] == 0) queue.push(v);
        }
    }

    // Nodes left over never reached indegree 0: they sit on or after a cycle.
    if ((int)order.size() < n) return {};
    return order;
}

import java.util.*;

class TopoSort {
    // Kahn's algorithm. Each edge {u, v} means u must come before v.
    // Returns an order of the nodes 0..n-1, or an empty array if there is a cycle.
    static int[] sort(int n, int[][] edges) {
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
        int[] indegree = new int[n];
        for (int[] e : edges) {
            adj.get(e[0]).add(e[1]);
            indegree[e[1]]++;
        }

        ArrayDeque<Integer> queue = new ArrayDeque<>();
        for (int v = 0; v < n; v++) {
            if (indegree[v] == 0) queue.add(v);
        }
        int[] order = new int[n];
        int size = 0;
        while (!queue.isEmpty()) {
            int u = queue.poll();
            order[size++] = u;
            for (int v : adj.get(u)) {                       // "remove" the edge u -> v
                indegree[v]--;
                if (indegree[v] == 0) queue.add(v);
            }
        }

        // Nodes left over never reached indegree 0: they sit on or after a cycle.
        if (size < n) return new int[0];
        return order;
    }
}

Why it’s O(V + E)

Each node enters and leaves the queue at most once: O(V). Each edge is looked at twice, once while counting indegree and once when it’s removed: O(E). Building the adjacency lists is O(V + E) too.

Space is the adjacency lists, O(V + E), plus indegree, the queue and order, each O(V).

If you need the smallest order in dictionary order, swap the queue for a min-heap. Each push and pop then costs O(log V), for O((V + E) log V) in total.

Common mistakes

for a, b in prereqs: adj[a].append(b); indegree[b] += 1   # ✗ a before b
for a, b in prereqs: adj[b].append(a); indegree[a] += 1   # ✓ b before a

if v not in seen: queue.append(v)    # ✗ ignores other prerequisites
if indegree[v] == 0: queue.append(v)  # ✓ waits for all of them

return order                              # ✗ silently incomplete
return order if len(order) == n else []   # ✓ report the cycle

Variations

• Course schedule. “Can you finish all courses?” is just the length check: len(order) == n. “In what order?” returns order itself.
• DFS-based topological sort. Run DFS and append each node after all its descendants finish. That post-order, reversed, is a topological order. To detect cycles, colour nodes white (unseen), grey (on the current path) and black (finished): an edge to a grey node closes a cycle.
• Longest path in a DAG. Walk the nodes in topological order and relax each outgoing edge with best[v] = max(best[v], best[u] + w). Every node is final before it’s used, so this runs in O(V + E), even though longest path is hard on general graphs.
• Parallel scheduling by levels. Instead of one node at a time, take the whole queue as a round. Everything in a round can run at the same time, and the number of rounds is the minimum number of semesters (or build stages) needed.
• Smallest order in dictionary order. Use a min-heap instead of the FIFO queue, so the smallest ready node always goes next.