Graph AlgosAlgorithmaka in-degree topological sort, BFS topological sort

Kahn's Algorithm

Topologically sort a DAG by repeatedly emitting vertices whose in-degree has dropped to zero; leftover vertices reveal a cycle.

▶ VisualizePattern: Breadth-First SearchPractice (2)
Progress

Overview

Kahn's algorithm produces a Topological Sort by peeling off sources: vertices with no incoming edges. It keeps an indeg[v] counter per vertex, starts with every vertex whose counter is zero, and each time it emits a vertex it decrements the counters of that vertex's successors. Whenever a counter reaches zero the vertex becomes a source and is enqueued.

The bookkeeping doubles as a cycle detector: vertices on or downstream of a cycle never reach in-degree zero, so they are never emitted. If the output has fewer than n vertices, the graph is not a DAG. This is the standard way to answer "can all courses be finished?".

Swapping the FIFO queue for a min-heap yields the lexicographically smallest topological order; swapping it for a max-heap, the largest. Processing the queue level by level (all current zero-in-degree vertices together) yields the minimum number of parallel rounds needed to finish every task.

topological sortin-degreequeueBFScycle detectionO(V + E)

Intuition

A mental model before the formal terms.

Each vertex holds a counter of "things I am still waiting for". Sources wait for nothing, so they go first. When a task finishes it taps every dependent on the shoulder and says "one fewer thing to wait for". A dependent whose counter hits zero is now free and joins the ready line. The order in which tasks leave the ready line is the topological order.

A cycle is a group of tasks each waiting on another member of the group. Nobody in the group ever gets tapped enough times to hit zero, so the ready line drains while they are still waiting. Counting how many tasks were served versus how many exist catches this without any explicit cycle search.

Example: edges 0→1, 0→2, 1→3, 2→3. In-degrees: [0, 1, 1, 2]. Queue starts [0]. Emit 0: indeg[1] = 0, indeg[2] = 0, queue [1, 2]. Emit 1: indeg[3] = 1. Emit 2: indeg[3] = 0, queue [3]. Emit 3. Order [0, 1, 2, 3], 4 of 4 emitted — a DAG.

How it works

  1. Build the adjacency list and indeg[v] = number of edges pointing into v. One pass over the edge list does both.
  2. Enqueue every vertex with indeg[v] == 0. If there are none and n > 0, every vertex is on a cycle.
  3. Pop u, append to order. For each v in adj[u], decrement indeg[v]; if it becomes zero, enqueue v. Never enqueue on a non-zero value and never enqueue twice — a vertex hits exactly zero once.
  4. When the queue is empty, compare order.length with n. Equal: valid topological order. Smaller: a cycle exists; the vertices with indeg > 0 are exactly the ones on cycles or reachable from cycles.
  5. For "minimum rounds": process the queue in batches — every vertex in the queue at the start of a round can run in that round.

Why it works

Invariant: indeg[v] equals the number of predecessors of v that have not yet been emitted. It is initialised to the total count and decremented exactly once per emitted predecessor.

A vertex is emitted only when the invariant says every predecessor has been emitted, so all edges into it point backwards in the output — the definition of a topological order.

Termination with all n vertices requires that every vertex eventually has all predecessors emitted. In a DAG this holds by induction on the longest path ending at v. On a cycle c1 → c2 → … → ck → c1, each ci waits for c(i-1), so none is ever emitted; hence a short output implies a cycle, and a cycle implies a short output.

Recognition

How to tell a problem wants this.

  • "Prerequisites", "dependencies", "must be completed before" with a directed edge list.
  • The problem asks for any valid ordering, whether one exists, or the lexicographically smallest one.
  • The problem asks how many "rounds" or "semesters" are needed when independent tasks can run in parallel (level-by-level Kahn).
  • Counting in-degrees is natural (e.g. "find the judge / celebrity" style questions also use degree counts).
“minimum steps” → Breadth-First Search“prerequisites” → Topological Sort

Interactive visualization

Play, step, change the input. ← → and space work too.

shirt0tie1jacket2pants0belt2shoes2socks0
Queue
shirtpantssocks
Topological order
empty
1/16Count incoming edges. Nodes with in-degree 0 have no prerequisites, so they can go first: shirt, pants, socks.
Current node (label = in-degree)In queue (in-degree 0)EmittedEdge being removedStuck in a cycle
PseudocodeLearn Kahn's Algorithm →
1indeg[v] = number of incoming edges
2queue = [v for v in nodes if indeg[v] == 0]
3while queue not empty:
4  u = queue.popleft(); order.append(u)
5  for v in neighbors(u):
6    indeg[v] -= 1
7    if indeg[v] == 0: queue.append(v)
8if len(order) < n: cycle detected
Complexity
best O(V + E)
avg O(V + E)
worst O(V + E)
space O(V)
Speed

Pseudocode

1indeg[v] = 0 for all v; for (u, v) in edges: adj[u].add(v); indeg[v] += 1
2queue = [v for v in 0..n-1 if indeg[v] == 0]
3order = []
4while queue not empty:
5  u = queue.popleft(); order.append(u)
6  for v in adj[u]:
7    indeg[v] -= 1
8    if indeg[v] == 0: queue.append(v)
9if len(order) != n: report cycle
10return order

Implementations

1import heapq
2from collections import deque
3 
4 
5def kahn(out: list[list[int]]) -> list[int]:
6    """Kahn's algorithm: peel off vertices whose dependencies are all
7    satisfied. BFS-flavoured, iterative, and it detects cycles for free.
8    Returns [] when the graph has a cycle."""
9    n = len(out)
10 
111 · Count incoming edges: indeg[v] is how many prerequisites v still has
12    indeg = [0] * n
13    for row in out:
14        for v in row:
15            indeg[v] += 1
16 
172 · Seed with everything that has no prerequisite at all
18    ready = deque(u for u, d in enumerate(indeg) if d == 0)
19 
203 · Emitting u satisfies one prerequisite for each of its successors
21    order: list[int] = []
22    while ready:
23        u = ready.popleft()
24        order.append(u)
25        for v in out[u]:
26            indeg[v] -= 1
27            if indeg[v] == 0:
28                ready.append(v)
29 
304 · Short output means some vertices never hit zero: they form a cycle
31    return order if len(order) == n else []
32 
33 
345 · Swap the deque for a min-heap to get the lexicographically smallest order
35def kahn_lexicographic(out: list[list[int]]) -> list[int]:
36    n = len(out)
37    indeg = [0] * n
38    for row in out:
39        for v in row:
40            indeg[v] += 1
41    ready = [u for u, d in enumerate(indeg) if d == 0]
42    heapq.heapify(ready)
43    order: list[int] = []
44    while ready:
45        u = heapq.heappop(ready)
46        order.append(u)
47        for v in out[u]:
48            indeg[v] -= 1
49            if indeg[v] == 0:
50                heapq.heappush(ready, v)
51    return order if len(order) == n else []
Walkthrough
  1. deque(u for u, d in enumerate(indeg) if d == 0) seeds the ready queue from a generator in a single expression.
  2. ready.popleft() is O(1) on a deque; the same code with a list and pop(0) would be O(V) per step.
  3. Python has no -- operator, so the decrement and the zero test are two statements — slightly longer, and arguably clearer.
  4. heapq.heapify(ready) turns the initial ready list into a heap in O(V) rather than V individual pushes at O(V log V).
  5. order if len(order) == n else [] is the cycle test; graphlib raises instead, which is the better contract.
Complexity (this implementation)
time O(V + E) with a deque; O(V log V + E) with the min-heap variant · space O(V)
Language notes
  • graphlib.TopologicalSorter (Python 3.9+) implements exactly this and raises CycleError rather than returning a sentinel — it is what production code should use.
  • heapq.heapify is Floyd O(n) construction; building the same heap with n heappush calls is O(n log n).
  • collections.deque.popleft is O(1); list.pop(0) is O(n) and is the standard way this algorithm accidentally becomes quadratic.
  • networkx.topological_sort returns a generator and also raises on a cyclic graph.
Common mistakes in this language
  • Using a list with pop(0) for the ready queue.
  • Building indeg as a dict from the edges alone, which omits vertices with no incoming edges and therefore never seeds the queue correctly.
  • Returning [] for both "cycle" and "empty graph" when graphlib already models the distinction properly.
Language differences that matter here
  • The ready queue needs collections.deque in Python and std::queue in C++, while JS/TS use an array plus head cursor because shift() is O(n).
  • The lexicographic variant needs a min-heap: heapq and std::priority_queue with std::greater supply one, while JavaScript falls back to a sorted array with an O(k) splice unless a heap is hand-written.
  • Only Python ships this algorithm in the standard library (graphlib.TopologicalSorter), and it is also the only one whose built-in version signals a cycle by raising rather than by returning a sentinel.
  • Decrement-and-test: C++ and JS/TS write --indeg[v] === 0 as one expression; Python has no decrement operator and needs two statements.

Complexity

Best
O(V + E)
Average
O(V + E)
Worst
O(V + E)
Space
O(V)

Heap variant for lexicographic order: O((V + E) log V).

Compare growth rates in the Complexity Explorer →

When to use — and when not to

Use it when
  • Any topological-sort task, especially when you also need to report cycles or the vertices involved in them.
  • Level-by-level scheduling ("how many semesters / parallel rounds").
  • Lexicographically smallest / largest valid order (use a heap).
  • Iterative code is required (no recursion depth concerns).
Avoid it when
  • You need DFS finish times for other purposes as well (e.g. computing SCCs) — DFS Topological Sort shares that DFS.
  • The graph has cycles by design and you want an order of the condensation — run Strongly Connected Components first.
  • Graph is undirected (no in-degrees in the relevant sense).

Alternatives

DFS Topological SortTopological Sort

Common mistakes

  • Enqueueing a vertex when its in-degree is *decremented* rather than when it *becomes zero* — duplicates and wrong order.
  • Not initialising the queue with all zero-in-degree vertices, including isolated ones.
  • Using queue.shift() on a JavaScript array in a hot loop (O(n) each); use a head index or a real deque.
  • Reversing edge direction when the input lists [course, prerequisite] pairs — the edge must go prerequisite → course.
  • Forgetting the final len(order) == n check, silently returning a partial order for cyclic input.

Interview patterns

  • Course Schedule II: return the order or an empty array if impossible.
  • Alien Dictionary: build character constraints, then Kahn with a min-heap if lexicographic output is required.
  • Parallel courses / minimum semesters: count levels.
  • Find all vertices that are "safe" (not on or leading to a cycle): run Kahn on the reversed graph; emitted vertices are safe.
Interview questions on this
Mock interviews

Example problems

Course SchedulemediumAlien Dictionaryhard