Topological sort: Kahn's algorithm

LeetCode 207 hands you a course catalog and a list of prerequisites. Course 1 needs course 0 first; course 3 needs both 1 and 2. Can a student finish all of them? The answer is yes whenever the dependency graph is a DAG, no whenever a cycle hides inside. Two thousand courses, five thousand prerequisites, and the function has to return a single boolean.

Two algorithms solve this. Both run in linear time. Either one works on the same inputs. They produce different but equally valid orderings, and they fail on cyclic input in the same way. So why two chapters? Because the moves the reader needs to learn are different. This chapter is Kahn’s algorithm: iterative, indegree-driven, queue-based. The next chapter is DFS post-order: recursive, finish-time-driven, stack-based. Pick Kahn first if you only have time for one. It is the safer interview default at LC’s input scale, and the indegree mental model lines up with the way prerequisites are usually phrased in the problem text itself.

What Kahn’s actually does

Take the dependency graph as a directed graph: an edge b -> a means b is a prerequisite of a. The indegree of a vertex is the number of incoming edges, which is the number of prereqs not yet satisfied. A vertex with indegree zero has no unsatisfied prereqs; it is ready. Take any such vertex, declare it the next course, and pretend you already finished it: every edge leaving it disappears, and that may free up new indegree-zero vertices for the next round.

Here is the reduction the chapter is built on. A topological order exists if and only if at every step there is at least one vertex with indegree zero in the remaining subgraph. Kahn’s algorithm makes this constructive by repeatedly extracting such a vertex and decrementing its successors’ indegrees. If the loop runs out of indegree-zero vertices before emitting all |V| of them, then a cycle is hiding among the leftovers: every vertex on a cycle has at least one prereq sitting on the same cycle, so none of them ever reaches indegree zero.

The dual purpose is the algorithm’s quietest virtue. One loop produces a topological order and detects a cycle, exactly, with no extra bookkeeping. LeetCode 207 is just a special case where the boolean len(order) == numCourses is the requested output.

The algorithm

Three phases. Build the indegree array and the adjacency list. Seed a queue with every vertex whose indegree is already zero. Then drain: pop one, emit it, decrement each successor’s indegree, and enqueue any successor whose count just hit zero. Stop when the queue is empty.

def can_finish(num_courses, prerequisites):
    indeg = [0] * num_courses
    adj = [[] for _ in range(num_courses)]
    for a, b in prerequisites:        # b -> a (b is the prereq)
        adj[b].append(a)
        indeg[a] += 1

    q = deque(v for v in range(num_courses) if indeg[v] == 0)
    visited = 0
    while q:
        u = q.popleft()
        visited += 1
        for v in adj[u]:
            indeg[v] -= 1
            if indeg[v] == 0:
                q.append(v)
    return visited == num_courses

# LC 207. Course Schedule
"""LC 207 Course Schedule: Kahn's algorithm reference."""
from collections import deque
from typing import List


def can_finish(num_courses: int, prerequisites: List[List[int]]) -> bool:
    """Return True iff all courses can be finished (the prereq graph is a DAG).

    Edge convention: prerequisites[i] = [a, b] means b must be taken before a,
    so the directed edge is b -> a in the dependency graph. Run a Kahn
    topological sort on (V, E) and report True iff we order all V vertices.
    """
    indeg = [0] * num_courses
    adj: List[List[int]] = [[] for _ in range(num_courses)]
    for a, b in prerequisites:
        adj[b].append(a)
        indeg[a] += 1

    q = deque(v for v in range(num_courses) if indeg[v] == 0)
    visited = 0
    while q:
        u = q.popleft()
        visited += 1
        for v in adj[u]:
            indeg[v] -= 1
            if indeg[v] == 0:
                q.append(v)
    return visited == num_courses

// LC 207. Course Schedule
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

public class Sol {
    public static boolean canFinish(int numCourses, int[][] prerequisites) {
        int[] indeg = new int[numCourses];
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) adj.add(new ArrayList<>());
        for (int[] e : prerequisites) {
            int a = e[0], b = e[1]; // b -> a
            adj.get(b).add(a);
            indeg[a]++;
        }
        Deque<Integer> q = new ArrayDeque<>();
        for (int v = 0; v < numCourses; v++) if (indeg[v] == 0) q.offer(v);
        int visited = 0;
        while (!q.isEmpty()) {
            int u = q.poll();
            visited++;
            for (int v : adj.get(u)) {
                if (--indeg[v] == 0) q.offer(v);
            }
        }
        return visited == numCourses;
    }
}

// LC 207. Course Schedule
#include <queue>
#include <vector>

class Solution {
public:
    bool canFinish(int numCourses, std::vector<std::vector<int>>& prerequisites) {
        std::vector<int> indeg(numCourses, 0);
        std::vector<std::vector<int>> adj(numCourses);
        for (const auto& e : prerequisites) {
            int a = e[0], b = e[1]; // b -> a
            adj[b].push_back(a);
            indeg[a]++;
        }
        std::queue<int> q;
        for (int v = 0; v < numCourses; ++v) if (indeg[v] == 0) q.push(v);
        int visited = 0;
        while (!q.empty()) {
            int u = q.front(); q.pop();
            ++visited;
            for (int v : adj[u]) {
                if (--indeg[v] == 0) q.push(v);
            }
        }
        return visited == numCourses;
    }
};

// LC 207. Course Schedule
package main

func canFinish(numCourses int, prerequisites [][]int) bool {
	indeg := make([]int, numCourses)
	adj := make([][]int, numCourses)
	for _, e := range prerequisites {
		a, b := e[0], e[1] // b -> a
		adj[b] = append(adj[b], a)
		indeg[a]++
	}
	q := make([]int, 0, numCourses)
	for v := 0; v < numCourses; v++ {
		if indeg[v] == 0 {
			q = append(q, v)
		}
	}
	visited := 0
	for len(q) > 0 {
		u := q[0]
		q = q[1:]
		visited++
		for _, v := range adj[u] {
			indeg[v]--
			if indeg[v] == 0 {
				q = append(q, v)
			}
		}
	}
	return visited == numCourses
}

The control flow has only one conditional that matters, and it is the indegree check on the decrement. Equality, not less-than-or-equal. With duplicate prereqs in the input the indegree may go negative; a <= 0 check then mis-fires on every subsequent decrement and starts re-enqueuing vertices that already left the queue. The verified Java, C++, and Go versions all use --indeg[v] == 0.

flowchart TD
    A[Build indeg + adjacency list] --> B[Seed queue: every v with indeg of v equals 0]
    B --> C{Queue empty?}
    C -->|no| D[Pop u; emit u; visited += 1]
    D --> E[For each successor v: indeg of v -= 1; if 0, enqueue]
    E --> C
    C -->|yes| F{visited == V?}
    F -->|yes| G[Return order - DAG]
    F -->|no| H[Return failure - cycle]

Worked example: LC 207 on a 6-course catalog

Six courses, seven prerequisites: 0 -> 1, 0 -> 2, 1 -> 3, 2 -> 3, 2 -> 4, 3 -> 5, 4 -> 5. The arrow 0 -> 1 means course 0 is a prereq of course 1.

Initial indegrees: [0, 1, 1, 2, 1, 2]. Vertex 0 is the only one ready, so the queue starts as [0].

flowchart LR
    n0((0)) --> n1((1))
    n0 --> n2((2))
    n1 --> n3((3))
    n2 --> n3
    n2 --> n4((4))
    n3 --> n5((5))
    n4 --> n5

Pop 0, emit 0. Decrement indegrees of 1 and 2; both hit zero, both go into the queue. The decisive moment lands on the second pop: when vertex 2 is processed, two successors (3 and 4) get a decrement, and only 4 becomes ready immediately while 3 still owes one prereq to vertex 1. The interleaving from there determines whether the emitted order is [0, 1, 2, 3, 4, 5], [0, 2, 1, 4, 3, 5], or one of the three other valid orderings; the FIFO queue makes the choice deterministic without making it canonical.

The widget animates each step: indegree array on the left, queue contents in the middle, the emitted order growing at the bottom. Step through it twice. The first pass to see the loop run; the second to notice that vertex 0 and vertex 5 always land at the same positions across every preset, while the middle three permute.

Interactive widget: Topological sort (Kahn’s vs DFS post-order) (panel panel-kahn), rendered on the website; the YAML spec describes the keyframes.

Static fallback: indegrees collapse [0,1,1,2,1,2] → [0,0,1,2,1,2] → [0,0,0,2,1,2] → [0,0,0,0,0,0] over the 16-step trace; emitted list grows [] → [0] → [0,1] → [0,1,2,3,4,5]; the final terminator records |emitted| == |V|, valid topological order.

What it actually costs

Each vertex is enqueued exactly once, the moment its indegree first reaches zero, and dequeued exactly once. Each directed edge (u, v) is relaxed exactly once, when the algorithm processes u and decrements indeg[v]. The total work is O(|V|) for vertex bookkeeping plus O(|E|) for edge bookkeeping.¹ The bound is tight: any topological-sort algorithm has to read every edge at least once to verify that the order respects it, so Ω(V + E) is the lower bound, and Kahn matches it within a constant.²

The space cost is dominated by the indegree array (O(V)) and the queue, which can hold up to V vertices at once when the input has no edges. Adjacency itself is O(V + E) but already counts as input.

When the pattern bends

The signature shape (graph given, run Kahn, return the answer) covers most of the rotation. Three variants change either the input or the termination condition. Each is its own LC problem, and each is a question about whether the reader can recognize Kahn under a different surface.

Reverse-graph Kahn for “safe nodes”

LC 802 asks which vertices have no path that ever enters a cycle. The natural inversion is to flip every edge, then run Kahn from the original-graph terminal vertices (out-degree zero in the original, indegree zero in the reverse). Every vertex Kahn emits in the reversed graph is safe, because in the original direction it has no descendant on a cycle.³

def eventual_safe_nodes(graph):
    n = len(graph)
    rev_indeg = [0] * n          # = original out-degree
    rev_adj = [[] for _ in range(n)]
    for u, succs in enumerate(graph):
        for v in succs:
            rev_adj[v].append(u)  # reverse edge: v -> u
            rev_indeg[u] += 1
    q = deque(v for v in range(n) if rev_indeg[v] == 0)
    safe = [False] * n
    while q:
        u = q.popleft()
        safe[u] = True
        for v in rev_adj[u]:
            rev_indeg[v] -= 1
            if rev_indeg[v] == 0:
                q.append(v)
    return [v for v in range(n) if safe[v]]

# LC 802. Find Eventual Safe States
"""LC 802 Find Eventual Safe States: reverse-graph Kahn."""
from collections import deque
from typing import List


def eventual_safe_nodes(graph: List[List[int]]) -> List[int]:
    """Return all vertices from which every path terminates (no cycle reachable).

    Insight: a vertex is safe iff in the *reversed* graph it can be emitted
    by Kahn starting from terminal vertices (out-degree zero in the original,
    indegree zero after reversal). Reverse all edges, seed Kahn from
    original-terminal vertices, return the emitted set sorted.
    """
    n = len(graph)
    rev_indeg = [0] * n          # = original out-degree
    rev_adj: List[List[int]] = [[] for _ in range(n)]
    for u, succs in enumerate(graph):
        for v in succs:
            rev_adj[v].append(u)  # reverse edge: v -> u
            rev_indeg[u] += 1     # u's reversed indegree = u's original out-degree

    q = deque(v for v in range(n) if rev_indeg[v] == 0)
    safe = [False] * n
    while q:
        u = q.popleft()
        safe[u] = True
        for v in rev_adj[u]:
            rev_indeg[v] -= 1
            if rev_indeg[v] == 0:
                q.append(v)
    return [v for v in range(n) if safe[v]]

// LC 802. Find Eventual Safe States
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

public class Sol {
    public static List<Integer> eventualSafeNodes(int[][] graph) {
        int n = graph.length;
        int[] revIndeg = new int[n];                // = original out-degree
        List<List<Integer>> revAdj = new ArrayList<>();
        for (int i = 0; i < n; i++) revAdj.add(new ArrayList<>());
        for (int u = 0; u < n; u++) {
            for (int v : graph[u]) {
                revAdj.get(v).add(u);                // reverse edge v -> u
                revIndeg[u]++;
            }
        }
        Deque<Integer> q = new ArrayDeque<>();
        for (int v = 0; v < n; v++) if (revIndeg[v] == 0) q.offer(v);
        boolean[] safe = new boolean[n];
        while (!q.isEmpty()) {
            int u = q.poll();
            safe[u] = true;
            for (int v : revAdj.get(u)) {
                if (--revIndeg[v] == 0) q.offer(v);
            }
        }
        List<Integer> ans = new ArrayList<>();
        for (int v = 0; v < n; v++) if (safe[v]) ans.add(v);
        return ans;
    }
}

// LC 802. Find Eventual Safe States
#include <queue>
#include <vector>

class Solution {
public:
    std::vector<int> eventualSafeNodes(std::vector<std::vector<int>>& graph) {
        int n = (int)graph.size();
        std::vector<int> revIndeg(n, 0);                  // = original out-degree
        std::vector<std::vector<int>> revAdj(n);
        for (int u = 0; u < n; ++u) {
            for (int v : graph[u]) {
                revAdj[v].push_back(u);                    // reverse edge v -> u
                revIndeg[u]++;
            }
        }
        std::queue<int> q;
        for (int v = 0; v < n; ++v) if (revIndeg[v] == 0) q.push(v);
        std::vector<bool> safe(n, false);
        while (!q.empty()) {
            int u = q.front(); q.pop();
            safe[u] = true;
            for (int v : revAdj[u]) {
                if (--revIndeg[v] == 0) q.push(v);
            }
        }
        std::vector<int> ans;
        for (int v = 0; v < n; ++v) if (safe[v]) ans.push_back(v);
        return ans;
    }
};

// LC 802. Find Eventual Safe States
package main

func eventualSafeNodes(graph [][]int) []int {
	n := len(graph)
	revIndeg := make([]int, n) // = original out-degree
	revAdj := make([][]int, n)
	for u, succs := range graph {
		for _, v := range succs {
			revAdj[v] = append(revAdj[v], u) // reverse edge v -> u
			revIndeg[u]++
		}
	}
	q := make([]int, 0, n)
	for v := 0; v < n; v++ {
		if revIndeg[v] == 0 {
			q = append(q, v)
		}
	}
	safe := make([]bool, n)
	for len(q) > 0 {
		u := q[0]
		q = q[1:]
		safe[u] = true
		for _, v := range revAdj[u] {
			revIndeg[v]--
			if revIndeg[v] == 0 {
				q = append(q, v)
			}
		}
	}
	ans := make([]int, 0)
	for v := 0; v < n; v++ {
		if safe[v] {
			ans = append(ans, v)
		}
	}
	return ans
}

The reversal is the entire interview value of LC 802. Without it the problem reduces to DFS with three-color marking, which is a different algorithm and a different chapter.

Char-pair edge construction (LC 269)

LC 269 hands you a list of strings, sorted lexicographically by an unknown alphabet, and asks for any total order on the characters consistent with the input. The graph is not given. You build it: pairwise-compare adjacent words, find their first differing position, add a directed edge between those two characters. Then run Kahn on a graph of at most 26 vertices and return any valid order. The edge case that bites is the invalid prefix: when words[i] is a strict longer prefix of words[i+1] (for example, ["abc", "ab"]), no character ordering can place "abc" before "ab", and the function returns "".⁴

Pseudo-Kahn on undirected leaves (LC 310)

LC 310 wants the centroid of an undirected tree: the vertex (or two vertices) you can root at to minimize the tree’s height. The trick is to peel leaves layer by layer. Initialize a queue with every vertex of degree 1; pop one, decrement its single neighbor’s degree, push the neighbor if its degree drops to 1; stop when fewer than three vertices remain. The leftover one or two are the centroids. The graph is undirected so “indegree” becomes “degree”, and the termination condition is <= 2 rather than zero, but the loop body is the same indegree-reduction loop Kahn runs on a DAG.

Two pitfalls that bite

A third bug is worth naming briefly because it shows up on Java and C++ submissions specifically: forgetting to pre-size the adjacency list. List<List<Integer>> adj = new ArrayList<>() creates an empty outer list, and adj.get(b).add(a) then throws IndexOutOfBoundsException because b was never allocated. Always loop numCourses times to add empty inner lists before any insertion. The C++ form std::vector<std::vector<int>> adj(numCourses) does this in one line.

Problem ladder

CORE (solve all three to claim chapter mastery)

• LC 207: Course Schedule [Medium] • topological-sort-kahn ★
• LC 210: Course Schedule II [Medium] • topological-sort-kahn
• LC 802: Find Eventual Safe States [Medium] • topological-sort-kahn-reverse-graph

STRETCH (optional)

• LC 269: Alien Dictionary [Hard] • topological-sort-kahn-char-graph (LeetCode Premium; the order-output mechanic is in CORE via LC 210)
• LC 310: Minimum Height Trees [Medium] • topological-sort-kahn-leaf-trim

LC 207 is the chapter’s signature problem and the one the worked example and widget animate. LC 210 is a one-line edit on top of LC 207: append to an order list on dequeue, return it when its length matches numCourses. LC 802 is the pattern’s first non-trivial variant; the reversal step is the entire interview value.

The Easy band is intentionally absent. Kahn’s algorithm has no canonical Easy LC problem; the closest candidates (LC 1971 reachability, LC 997 town judge) test in/out-degree counting, not the indegree-decrement loop, and would teach the wrong pattern.

Where this leads

The dual chapter Topological sort: DFS post-order solves the same problems on the same inputs with a different algorithm, and the side-by-side widget panel renders both runs on this chapter’s 6-node DAG so the divergence in the middle three positions is visible at a glance. A “pick between them” decision table lives at the close of 8.5 once the reader has both algorithms in hand.

Past that, Cycle detection in graphs reuses Kahn’s emit-count test as one of three canonical cycle tests; the BFS-side machinery is identical.

References