Topological Sort (Kahn's Algorithm)

Advanced Graph theory. Essential for processing nodes with prerequisite dependencies (like Course Schedule).

Recognition

  • Tasks have prerequisites or directed dependencies.
  • You need a valid order or to detect a cycle in a DAG-like graph.

When not to use it

Do not force this pattern when the input is unordered and hashing is enough.

Avoid coding the template before naming the invariant you need to preserve.

Logic template

Python

from collections import deque

def topo_sort(nodes, edges):
    adj = {i: [] for i in nodes}
    in_degree = {i: 0 for i in nodes}
    for u, v in edges:
        adj[u].append(v)
        in_degree[v] += 1
        
    queue = deque([i for i in nodes if in_degree[i] == 0])
    res = []
    
    while queue:
        u = queue.popleft()
        res.append(u)
        for v in adj[u]:
            in_degree[v] -= 1
            if in_degree[v] == 0:
                queue.append(v)
    return res if len(res) == len(nodes) else []

JavaScript

function topoSort(nodes, edges) {
  const adj = new Map(nodes.map(i => [i, []]));
  const inDegree = new Map(nodes.map(i => [i, 0]));
  
  for (const [u, v] of edges) {
    adj.get(u).push(v);
    inDegree.set(v, inDegree.get(v) + 1);
  }
  
  const queue = [];
  for (const [node, degree] of inDegree.entries()) {
    if (degree === 0) queue.push(node);
  }
  
  const res = [];
  while (queue.length > 0) {
    const u = queue.shift();
    res.push(u);
    for (const v of adj.get(u)) {
      inDegree.set(v, inDegree.get(v) - 1);
      if (inDegree.get(v) === 0) queue.push(v);
    }
  }
  return res.length === nodes.length ? res : [];
}

Typically better than the obvious O(N^2) approach; verify with the template.

  • Name what stays true after every move.
  • Track the exact condition that lets you discard work safely.

Worked example

Recognition drill

Identify the reusable state and the rule that advances it.

  1. Restate the goal in one sentence.
  2. Name the moving parts and what they represent.
  3. Write the loop invariant before coding.
  4. Trace one failing case that breaks a naive approach.

Result: You can explain when to reach for the pattern and when to abandon it.

Common pitfalls

  • Off-by-one updates on loop bounds.
  • Updating state after comparing instead of before.
  • Confusing “solved once” with pattern mastery.

Related practice problems