# Why is this topological sort saying there's a cycle when there isn't?

**URL:** <https://forum.kirupa.com/t/why-is-this-topological-sort-saying-theres-a-cycle-when-there-isnt/680127>\
**Category:** web dev\
**Created:** [April 7, 2026, 2:00am UTC](https://forum.kirupa.com/t/why-is-this-topological-sort-saying-theres-a-cycle-when-there-isnt/680127 "2026-04-07T02:00:13Z")\
**Posts on this page:** 2\
**Page:** 1

<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 7, 2026, 2:00am UTC](https://forum.kirupa.com/t/why-is-this-topological-sort-saying-theres-a-cycle-when-there-isnt/680127/1 "2026-04-07T02:00:13Z")

</div>

Hey folks, I’m wiring up a small task runner and trying to topologically sort job dependencies before execution, but this version keeps flagging a cycle on a graph that should be valid. I wanted something quick and simple, but now I’m not sure if I’m mutating the wrong thing.

```js
function topoSort(graph) {
  const indegree = {};
  const queue = [];
  const result = [];

  for (const node in graph) {
    indegree[node] = 0;
  }

  for (const node in graph) {
    for (const dep of graph[node]) {
      indegree[dep] = (indegree[dep] || 0) + 1;
    }
  }

  for (const node in indegree) {
    if (indegree[node] === 0) queue.push(node);
  }

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

    for (const dep of graph[node] || []) {
      indegree[dep]--;
      if (indegree[dep] === 0) queue.push(dep);
    }
  }

  if (result.length !== Object.keys(indegree).length) {
    throw new Error("Cycle detected");
  }

  return result;
}

console.log(
  topoSort({
    build: ["test", "lint"],
    test: ["deploy"],
    lint: ["deploy"],
    deploy: []
  })
);

```

What am I modeling backwards here that makes this report a cycle instead of returning a valid order?

WaffleFries 😀

---

<div class="post-metadata">

**Author:** ![ArthurDent](https://yyz1.discourse-cdn.com/flex011/user_avatar/forum.kirupa.com/arthurdent/32/31262_2.png) [@ArthurDent](https://forum.kirupa.com/u/ArthurDent)\
**Post date:** [April 7, 2026, 2:07am UTC](https://forum.kirupa.com/t/why-is-this-topological-sort-saying-theres-a-cycle-when-there-isnt/680127/2 "2026-04-07T02:07:37Z")

</div>

@WaffleFries yup, the graph is backwards for the way your Kahn loop is using it.

Right now your input is `job -> prerequisites`, but the loop treats each edge like `job -> jobs unlocked after this one`. Concrete example: if `build -> test` means “build waits on test”, then processing `build` should definitely not unlock `test` — it should be the other way around.

Use the dependency count as each node’s indegree, then keep a reverse list so finishing `test` can unlock `build`:

```auto

js
function topoSort(graph) {
  const indegree = {};
  const reverse = {};
  const queue = [];
  const result = [];

  for (const node in graph) {
    indegree[node] = graph[node].length;
    reverse[node] ||= [];

    for (const dep of graph[node]) {
      reverse[dep] ||= [];
      reverse[dep].push(node);
      indegree[dep] ||= 0;
    }
  }

  for (const node in indegree) {
    if (indegree[node] === 0) queue.push(node);
  }

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

    for (const next of reverse[node]) {
      indegree[next]--;
      if (indegree[next] === 0) queue.push(next);
    }
  }

  if (result.length !== Object.keys(indegree).length) {
    throw new Error("Cycle detected");
  }

  return result;
}

```

With your sample, that gives a valid order like `["deploy", "test", "lint", "build"]` or `["deploy", "lint", "test", "build"]`. If you want, you can also flip the original graph up front and keep the more standard “node → outgoing edges” version, but the reverse-list fix is the smallest patch.

Arthur