Topological Sort

How it works, step by step

1. 1

   Count the incoming arrows of every node - its in-degree. That is how many prerequisites it still waits for.

2. 2

   Put every node with in-degree 0 into a ready queue. Nothing blocks them.

3. 3

   Take a node out of the queue and append it to the order. It is now scheduled.

4. 4

   Remove its outgoing arrows: each target's in-degree drops by 1. Any target that reaches 0 has all prerequisites met - it joins the queue.

5. 5

   Repeat until the queue is empty. Every node and edge is touched once - O(V + E).

6. 6

   If the finished order holds all V nodes, you have a valid schedule. If it is shorter, the leftover nodes sit in (or behind) a cycle - no valid order exists.

The code, in JavaScript

function topoSort(graph) {
  // graph: { node: [nodes it points to] }
  const indegree = {};
  for (const node in graph) indegree[node] ??= 0;
  for (const node in graph) {
    for (const next of graph[node]) {
      indegree[next] = (indegree[next] ?? 0) + 1;
    }
  }

  // Start with every node that has no prerequisites.
  const queue = Object.keys(indegree).filter((n) => indegree[n] === 0);
  const order = [];

  while (queue.length > 0) {
    const node = queue.shift();
    order.push(node);                  // safe: nothing blocks it anymore

    for (const next of graph[node] ?? []) {
      indegree[next] -= 1;             // one prerequisite done
      if (indegree[next] === 0) {
        queue.push(next);              // last blocker gone - ready
      }
    }
  }

  return order;
}

const pipeline = {
  A: ["B", "E"], B: ["F"], C: ["B", "D"], D: ["F"],
  E: ["G"], F: ["G"], G: [],
};

topoSort(pipeline);   // → ["A", "C", "E", "B", "D", "F", "G"]

Dry run: scheduling the 7-job pipeline

The same steps the visualizer plays, written as a table. Generated by running the real algorithm - not written by hand.

• Only a DAG has a topological order. One cycle anywhere and the honest answer is 'impossible'. Kahn's detects this for free: if the finished order has fewer than V nodes, there is a cycle - no extra code, just count.
• Many valid orders usually exist. A test that asserts one exact output is brittle - it breaks when someone reorders an object or swaps the queue for a stack. Assert the property instead: every edge's source appears before its target.
• Need a deterministic, repeatable order? Use a min-heap instead of a plain queue and you get the lexicographically smallest valid order - handy when two machines must produce identical schedules.
• In the DFS version, push the node AFTER visiting its neighbours (post-order), then reverse at the end. Pushing before the recursion looks almost identical, runs without errors, and silently returns a wrong order.

Topological Sort vs. its closest relatives