Why does this topological sort sometimes return an incomplete order even when the graph is acyclic?

programming web dev
1

I’m implementing Kahn’s algorithm for course scheduling, but on some acyclic inputs the result is missing nodes. I expected all vertices to appear once. What is wrong with how I’m building or updating indegrees here?

function topo(n, edges) {
  const indeg = Array(n).fill(0), g = Array.from({ length: n }, () => []), q = [], out = [];
  for (const [a, b] of edges) { g[a].push(b); indeg[a]++; }
  for (let i = 0; i < n; i++) if (indeg[i] === 0) q.push(i);
  while (q.length) {
    const cur = q.shift(); out.push(cur);
    for (const nxt of g[cur]) if (--indeg[nxt] === 0) q.push(nxt);
  }
  return out;
}

Ellen

2

Your indeg is currently counting outgoing edges from a, not incoming edges into b.

Kahn’s algorithm starts from nodes with no incoming edges, then removes outgoing edges as those nodes are processed. With indeg[a]++, your queue is seeded from the wrong side of the graph, so some nodes never become ready when they should.

The smallest fix is this:

indeg[b]++; // not indeg[a]++
function topo(n, edges) {
  const indeg = Array(n).fill(0),
        g = Array.from({ length: n }, () => []),
        q = [],
        out = [];

  for (const [a, b] of edges) {
    g[a].push(b);
    indeg[b]++; // count incoming edges for b
  }

  for (let i = 0; i < n; i++) {
    if (indeg[i] === 0) q.push(i);
  }

  while (q.length) {
    const cur = q.shift();
    out.push(cur);

    for (const nxt of g[cur]) {
      if (--indeg[nxt] === 0) q.push(nxt);
    }
  }

  return out;
}

That indeg[b]++ line now matches --indeg[nxt] later:

  • indeg[b]++ records how many prerequisites point into each destination node.
  • --indeg[nxt] === 0 ensures nxt enters q only after all its incoming edges have been removed.

So the queue tracks exactly the nodes that are ready.

You can see it on a small acyclic graph:

function topo(n, edges) {
  const indeg = Array(n).fill(0),
        g = Array.from({ length: n }, () => []),
        q = [],
        out = [];

  for (const [a, b] of edges) {
    g[a].push(b);
    indeg[b]++;
  }

  for (let i = 0; i < n; i++) {
    if (indeg[i] === 0) q.push(i);
  }

  while (q.length) {
    const cur = q.shift();
    out.push(cur);

    for (const nxt of g[cur]) {
      if (--indeg[nxt] === 0) q.push(nxt);
    }
  }

  return out;
}

console.log(topo(4, [[0, 1], [0, 2], [1, 3], [2, 3]]));
// expected: [0, 1, 2, 3] or [0, 2, 1, 3]

If you want a tiny guard for cycles, out.length !== n is the signal.

Sora

3

@sora’s out.length !== n check is the useful debug signal here: if that trips on a graph you think is acyclic, your indegree build and edge direction probably disagree somewhere upstream, not the queue loop itself.

WaffleFries