Why does this DFS cycle check miss a loop in a directed graph?

programming web dev
1

Hey everyone, I’m working on a course scheduler toy app and trying to reject prerequisite lists that contain cycles, but this DFS version seems to pass some bad input and I’d rather not switch to a slower-feeling brute force check.

function hasCycle(graph) {
  const visited = new Set();
  const path = new Set();

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

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

    path.delete(node);
    return false;
  }

  for (const node in graph) {
    if (path.has(node)) return true;
    if (dfs(node)) return true;
  }

  return false;
}

console.log(hasCycle({
  A: ["B"],
  B: ["C"],
  C: ["A"]
}));

What am I checking in the wrong place here that makes a real cycle slip through?

WaffleFries

2

Your DFS is currently treating a revisit to an active ancestor as an already-finished node, not a cycle.

In a directed graph, the real cycle signal is reaching a node that is still on the current recursion stack. Right now visited.has(node) runs first, so when C -> A happens, A gets treated as done instead of “still in progress.” The outer path.has(node) check does not help because the important check has to happen during recursion, not after it returns.

The smallest fix is this:

if (path.has(node)) return true;
if (visited.has(node)) return false;
function dfs(node) {
  if (path.has(node)) return true;
  if (visited.has(node)) return false;

  visited.add(node);
  path.add(node);

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

  path.delete(node);
  return false;
}

With path.has(node) checked before visited.has(node):

  • path.has(node) catches the back-edge immediately when recursion walks back into an ancestor on the current DFS chain.
  • visited.has(node) ensures fully processed nodes are skipped without hiding active-path cycles.

That is the standard directed-graph DFS cycle check.

Using the same hasCycle, visited, and path setup, this now behaves correctly:

function hasCycle(graph) {
  const visited = new Set();
  const path = new Set();

  function dfs(node) {
    if (path.has(node)) return true;
    if (visited.has(node)) return false;

    visited.add(node);
    path.add(node);

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

    path.delete(node);
    return false;
  }

  for (const node in graph) {
    if (dfs(node)) return true;
  }

  return false;
}

console.log(hasCycle({ A: ["B"], B: ["C"], C: ["A"] })); // true
console.log(hasCycle({ A: ["B"], B: ["C"], C: [] }));    // false
console.log(hasCycle({ A: ["A"] }));                     // true

Tiny practical snippet: a self-loop like A -> A should also return true, and it now does.

Yoshiii