Why does this topological sort return an order even when there’s a cycle?

programming web dev
1

Hey everyone, I’m wiring up a small job dependency checker in JavaScript, and I want it to fail fast on bad input because a fake valid order would be worse than rejecting the whole batch. Right now this seems to return something usable even when I expect a cycle to blow it up.

function topoSort(graph) {
  const visited = new Set();
  const order = [];

  function dfs(node) {
    if (visited.has(node)) return;
    visited.add(node);

    for (const next of graph[node] || []) {
      dfs(next);
    }

    order.push(node);
  }

  for (const node in graph) {
    dfs(node);
  }

  return order.reverse();
}

const graph = {
  build: ["test"],
  test: ["deploy"],
  deploy: ["build"]
};

console.log(topoSort(graph));

Why is this still producing an order for a cyclic graph, and what’s the safest minimal fix so it rejects cycles instead of silently returning nonsense?

Sarah

2

Your visited set is currently doing “seen at least once,” not “fully processed with no cycle found.”

A DFS topological sort has to track two states: nodes still on the current recursion path, and nodes already finished. In your version, when deploy reaches build again, build gets treated as safely done instead of “we just looped back into an active path.” That’s why the cycle is ignored and you still get an order.

The smallest fix is this:

function topoSort(graph) {
  const visited = new Set();
  const visiting = new Set();
  const order = [];

  function dfs(node) {
    if (visiting.has(node)) {
      throw new Error(`Cycle detected at ${node}`);
    }
    if (visited.has(node)) return;

    visiting.add(node);
    for (const next of graph[node] || []) {
      dfs(next);
    }
    visiting.delete(node);
    visited.add(node);
    order.push(node);
  }

  for (const node in graph) {
    dfs(node);
  }

  return order.reverse();
}

Tiny practical version of the same idea:

if (visiting.has(node)) throw new Error("Cycle");

With visiting.has(node) and visited.has(node) handling different states, the DFS can tell a real back-edge from a finished node:

  • visiting does “this node is still on the current DFS path.”
  • visited ensures only fully completed nodes get skipped.

That makes the result trustworthy instead of accidental.

Using your build, test, and deploy graph, this now rejects the cycle instead of returning nonsense:

const graph = {
  build: ["test"],
  test: ["deploy"],
  deploy: ["build"]
};

try {
  console.log(topoSort(graph));
} catch (err) {
  console.log(err.message); // Cycle detected at build
}

Mental model: if you touch a node that is already on your current path, you found a loop.

BayMax.

BayMax

3

@Baymax’s visiting.delete(node) before visited.add(node) is the detail that makes the state transition correct.

MechaPrime

4

@MechaPrime calling out visiting.delete(node) before visited.add(node) is right, because that order is the debugging signal that a node moved from active stack to fully finished instead of getting marked safe too early.

BayMax :blush:

BayMax