Kahn’s Algorithm

Kahn’s algorithm (1962) is the most intuitive topological sort. The idea is exactly what you’d do by hand:

Find a task with no remaining prerequisites. Do it. Cross it off everyone else’s prerequisite list. Repeat until everything is done — or until something with prerequisites remains, in which case there’s a cycle.

In graph language: find a node with indegree 0. Emit it. Decrement the indegree of every neighbor. If a neighbor’s indegree hits zero, it’s now eligible. Repeat.

It’s BFS in disguise — the queue holds “currently eligible” nodes, and we expand by emitting and decrementing.

The template

1. Build adjacency list adj and indegree[] from edges.
2. Initialize queue with every v where indegree[v] == 0.
3. While queue is nonempty:
     u = queue.pop()
     append u to output
     for each edge u -> v:
         indegree[v] -= 1
         if indegree[v] == 0:
             queue.push(v)
4. If len(output) == V, return output.
   Else, the graph has a cycle.

Four lines of pseudocode, all O(V + E).

The full code

vector<int> topoSortKahn(int n, vector<vector<int>>& edges) {
    vector<vector<int>> adj(n);
    vector<int> indeg(n, 0);
    for (auto& e : edges) {
        adj[e[0]].push_back(e[1]);
        indeg[e[1]]++;
    }
    queue<int> q;
    for (int i = 0; i < n; i++) if (indeg[i] == 0) q.push(i);
    vector<int> out;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        out.push_back(u);
        for (int v : adj[u]) {
            if (--indeg[v] == 0) q.push(v);
        }
    }
    if ((int)out.size() != n) return {};                  // cycle: empty result
    return out;
}

from collections import deque
 
def topo_sort_kahn(n, edges):
    adj = [[] for _ in range(n)]
    indeg = [0] * n
    for u, v in edges:
        adj[u].append(v)
        indeg[v] += 1
    q = deque(i for i in range(n) if indeg[i] == 0)
    out = []
    while q:
        u = q.popleft()
        out.append(u)
        for v in adj[u]:
            indeg[v] -= 1
            if indeg[v] == 0:
                q.append(v)
    return out if len(out) == n else []                   # cycle: empty

public int[] topoSortKahn(int n, int[][] edges) {
    List<List<Integer>> adj = new ArrayList<>();
    for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
    int[] indeg = new int[n];
    for (int[] e : edges) {
        adj.get(e[0]).add(e[1]);
        indeg[e[1]]++;
    }
    Deque<Integer> q = new ArrayDeque<>();
    for (int i = 0; i < n; i++) if (indeg[i] == 0) q.offer(i);
    int[] out = new int[n];
    int k = 0;
    while (!q.isEmpty()) {
        int u = q.poll();
        out[k++] = u;
        for (int v : adj.get(u)) {
            if (--indeg[v] == 0) q.offer(v);
        }
    }
    return (k == n) ? out : new int[0];
}

Time: O(V + E). Space: O(V + E) for the adjacency list and indegree array.

Why it works (proof in two paragraphs)

Correctness: every node we emit has indegree 0 at the moment we emit it — meaning all its prerequisites are already in the output. So for every edge u → v, u appears before v: that’s the definition of a topological order.

Completeness on DAGs: if there’s no cycle, at least one node has indegree 0 at every step. Proof by contradiction: if every remaining node had indegree >= 1, you could trace edges backward from any node and never run out — but with finitely many nodes, you’d eventually revisit a node, forming a cycle. Contradiction. So we always have something to emit, and we emit every node exactly once.

Stepping through an example

Consider the graph with edges:

5 → 0, 5 → 2, 4 → 0, 4 → 1, 2 → 3, 3 → 1

Initial indegrees: [2, 2, 1, 1, 0, 0] (for nodes 0..5).

Final output: [4, 5, 1, 0, 2, 3] — a valid topo order. Other orders are equally valid; which one comes out depends on the order we initially push zero-indegree nodes.

Variation 1 — Lexicographically smallest topo order

Replace the FIFO queue with a min-heap. When multiple nodes have indegree 0, the heap returns the smallest one first.

import heapq
 
def topo_sort_lex(n, edges):
    adj = [[] for _ in range(n)]
    indeg = [0] * n
    for u, v in edges:
        adj[u].append(v)
        indeg[v] += 1
    heap = [i for i in range(n) if indeg[i] == 0]
    heapq.heapify(heap)
    out = []
    while heap:
        u = heapq.heappop(heap)
        out.append(u)
        for v in adj[u]:
            indeg[v] -= 1
            if indeg[v] == 0:
                heapq.heappush(heap, v)
    return out if len(out) == n else []

Time: O((V + E) log V) because of the heap operations.

This is the trick behind Alien Dictionary when the problem wants a deterministic answer.

Variation 2 — Parallel scheduling depth

Tasks have prerequisites. If we can run any number of tasks in parallel as long as their prerequisites are done, what’s the minimum number of time-steps to finish all tasks?

The answer is the length of the longest path in the DAG. Equivalently, the number of “rounds” in a level-by-level Kahn’s:

• Round 0: all nodes with indegree 0.
• Round 1: all nodes whose indegree became 0 after round 0 emissions.
• …

Tweak Kahn’s to track levels:

from collections import deque
 
def min_time_to_finish(n, edges):
    adj = [[] for _ in range(n)]
    indeg = [0] * n
    for u, v in edges:
        adj[u].append(v); indeg[v] += 1
    q = deque(i for i in range(n) if indeg[i] == 0)
    rounds = 0
    done = 0
    while q:
        rounds += 1
        for _ in range(len(q)):
            u = q.popleft()
            done += 1
            for v in adj[u]:
                indeg[v] -= 1
                if indeg[v] == 0:
                    q.append(v)
    return rounds if done == n else -1

Same O(V + E) as plain Kahn’s, plus a per-round bookkeeping. This is Parallel Courses I on LeetCode.

Variation 3 — Count distinct topo orders

Multiple valid orders may exist. Counting them is #P-hard in general (no polynomial algorithm known unless P = NP). For small graphs, you can enumerate via backtracking over “which zero-indegree node to pick next.”

Common bugs

Quick check

Next: DFS topological sort — the recursive variant, post-order emission, and the elegance of a single DFS.