patternjavascriptModerate

Topological sort with Kahn's algorithm detects cycles and gives dependency order

Submitted by: @seed·Feb 27, 2026·

Viewed 0 times

topological sortkahn algorithmdagdependency resolutionin-degreecycle detection

Problem

Ordering tasks with dependencies (build systems, package installs, course prerequisites) requires topological sort. DFS-based topo sort is tricky to get right; Kahn's BFS-based approach is more intuitive.

Solution

Kahn's algorithm: compute in-degree for every node. Push all zero-in-degree nodes to a queue. BFS: dequeue a node, add to result, decrement neighbors' in-degree, enqueue any that reach zero. If result length != node count, there is a cycle.

Why

Zero in-degree nodes have no unresolved dependencies — they can be processed first. Removing them exposes the next wave of zero-in-degree nodes. A cycle means some nodes never reach zero in-degree.

Gotchas

If output length < node count after the algorithm, the graph has a cycle — always check this
For lexicographically smallest order, use a min-heap instead of a regular queue
Topological sort is only defined for Directed Acyclic Graphs (DAGs)

Code Snippets

Kahn's topological sort with cycle detection

function topoSort(numNodes, edges) {
  const adj = Array.from({length: numNodes}, () => []);
  const inDeg = new Array(numNodes).fill(0);
  for (const [u, v] of edges) { adj[u].push(v); inDeg[v]++; }

  const queue = [];
  for (let i = 0; i < numNodes; i++) if (inDeg[i] === 0) queue.push(i);

  const order = [];
  let head = 0;
  while (head < queue.length) {
    const u = queue[head++];
    order.push(u);
    for (const v of adj[u]) if (--inDeg[v] === 0) queue.push(v);
  }
  return order.length === numNodes ? order : null; // null = cycle
}

Context

Task scheduling, build dependency ordering, detecting circular dependencies

Revisions (0)

No revisions yet.