Topological sort and dependency order

Given a directed acyclic graph of dependencies, a topological order lists every vertex before all the vertices it points to. Build systems, package managers, course prerequisites, task schedulers and spreadsheet recalculation all run this algorithm.

Kahn's algorithm — BFS on in-degrees

Repeatedly take a vertex with nothing left pointing at it.

function topologicalSort(graph) {
  const inDegree = new Map([...graph.keys()].map((node) => [node, 0]));

  for (const [, edges] of graph) {
    for (const next of edges) inDegree.set(next, (inDegree.get(next) ?? 0) + 1);
  }

  // Everything with no remaining prerequisites can start now.
  const queue = [...inDegree].filter(([, degree]) => degree === 0).map(([node]) => node);
  const order = [];

  while (queue.length) {
    const node = queue.shift();
    order.push(node);

    for (const next of graph.get(node) ?? []) {
      inDegree.set(next, inDegree.get(next) - 1);
      if (inDegree.get(next) === 0) queue.push(next);      // its last blocker cleared
    }
  }

  // Anything left is stuck in a cycle.
  return order.length === inDegree.size ? order : null;
}

O(V + E). The length check at the end is the cycle detector — a graph with a cycle can never drain the queue. Returning null rather than a partial order is the honest interface.

DFS alternative

Run DFS and push each vertex onto a list after its descendants finish; reverse the list. It is shorter, and it detects cycles with the three-colour scheme from the previous lesson.

Where it pays

• Build order. Compile dependencies before dependents.
• Task scheduling. With parallelism: everything at in-degree zero can run simultaneously, so the number of Kahn rounds is the minimum number of stages.
• Course prerequisites. "Can this curriculum be finished?" is the cycle check.
• Deadlock detection. A cycle in a resource-wait graph is a deadlock.

The follow-ups

Ask about uniqueness: an order is unique only if exactly one vertex has in-degree zero at every step. Otherwise many valid orders exist, and if the question wants the lexicographically smallest, swap the queue for a min-heap.

For a DAG, the same in-degree sweep also gives the longest path in linear time — which is the critical path of a project schedule, and one of the few graphs where longest path is not intractable.