Topological sort

Orders tasks so every task comes after the tasks it depends on. Only possible if there are no cycles.

How it works

Kahn's algorithm: count incoming edges (indegree) for each node. Start with every node at zero, meaning nothing blocks it. Take one, add it to the order, and lower the indegree of its neighbours; any that hit zero become ready. If the order ends up shorter than the number of nodes, the rest are stuck in a cycle.

Reach for it when

• Task or job dependencies
• Course prerequisites
• Build order
• Detect circular dependencies

Copy// edges [a, b] mean "a must happen before b". Returns an order, or null if there's a cycle.
function topoSort(n, edges) {
  const adj = buildGraph(n, edges, true),
    indegree = new Array(n).fill(0);
  for (const [, b] of edges) indegree[b]++;
  const ready = []; // nothing left blocking these
  for (let i = 0; i < n; i++) if (indegree[i] === 0) ready.push(i);
  const order = [];
  for (let h = 0; h < ready.length; h++) {
    const u = ready[h];
    order.push(u);
    for (const v of adj[u]) if (--indegree[v] === 0) ready.push(v);
  }
  return order.length === n ? order : null; // leftovers = stuck in a cycle
}

Traps

• Many valid orders can exist. Don't promise a specific one unless you sort the ready list.
• Edge direction: define 'a before b' out loud.