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

**URL:** <https://forum.kirupa.com/t/why-does-this-topological-sort-sometimes-return-an-incomplete-order-even-when-the-graph-is-acyclic/680059>\
**Category:** web dev\
**Created:** [April 5, 2026, 8:00pm UTC](https://forum.kirupa.com/t/why-does-this-topological-sort-sometimes-return-an-incomplete-order-even-when-the-graph-is-acyclic/680059 "2026-04-05T20:00:11Z")\
**Posts on this page:** 3\
**Page:** 1

<div class="post-metadata">

**Author:** ![Ellen1979](https://yyz1.discourse-cdn.com/flex011/user_avatar/forum.kirupa.com/ellen1979/32/31260_2.png) [@Ellen1979](https://forum.kirupa.com/u/Ellen1979)\
**Post date:** [April 5, 2026, 8:00pm UTC](https://forum.kirupa.com/t/why-does-this-topological-sort-sometimes-return-an-incomplete-order-even-when-the-graph-is-acyclic/680059/1 "2026-04-05T20:00:11Z")

</div>

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?

```js
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

---

<div class="post-metadata">

**Author:** ![sora](https://yyz1.discourse-cdn.com/flex011/user_avatar/forum.kirupa.com/sora/32/31259_2.png) [@sora](https://forum.kirupa.com/u/sora)\
**Post date:** [April 5, 2026, 8:14pm UTC](https://forum.kirupa.com/t/why-does-this-topological-sort-sometimes-return-an-incomplete-order-even-when-the-graph-is-acyclic/680059/2 "2026-04-05T20:14:26Z")

</div>

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:

```js
indeg[b]++; // not indeg[a]++
```

```js
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:

```js
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

---

<div class="post-metadata">

**Author:** ![WaffleFries](https://yyz1.discourse-cdn.com/flex011/user_avatar/forum.kirupa.com/wafflefries/32/31185_2.png) [@WaffleFries](https://forum.kirupa.com/u/WaffleFries)\
**Post date:** [April 5, 2026, 9:21pm UTC](https://forum.kirupa.com/t/why-does-this-topological-sort-sometimes-return-an-incomplete-order-even-when-the-graph-is-acyclic/680059/3 "2026-04-05T21:21:06Z")

</div>

@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