Topological Sort

A topological sort lines up the vertices of a directed acyclic graph (DAG) so that every arrow points forward — if there's an edge A → B, then A appears before B. It's the answer to any 'what order can I do these in?' question where some tasks must precede others: course prerequisites, build dependencies, spreadsheet recalculation.

Kahn's algorithm — peel off the ready nodes

The key number is each vertex's in-degree: how many arrows point *into* it — its count of unmet prerequisites. A vertex with in-degree 0 has nothing blocking it, so it's safe to output now. Output it, remove its outgoing edges (which lowers its neighbours' in-degrees), and that may free up new zero-in-degree vertices.

1. 1Compute the in-degree of every vertex.
2. 2Put all in-degree-0 vertices into a queue — they have no prerequisites.
3. 3Dequeue a vertex, append it to the output order.
4. 4For each of its out-neighbours, decrement their in-degree; if one hits 0, enqueue it.
5. 5Repeat until the queue empties.

function kahn(V, adj) {
  const indeg = Array(V).fill(0);
  for (let u = 0; u < V; u++) for (const v of adj[u]) indeg[v]++;
  const queue = [];
  for (let u = 0; u < V; u++) if (indeg[u] === 0) queue.push(u);
  const order = [];
  while (queue.length) {
    const u = queue.shift();
    order.push(u);
    for (const v of adj[u]) if (--indeg[v] === 0) queue.push(v);
  }
  return order.length === V ? order : null; // null => a cycle exists
}