Why does this DFS-based cycle check miss a back edge in a directed graph?

programming web dev
1

I’m detecting cycles in a directed graph with DFS, but some graphs with an obvious cycle return false. I suspect my visited bookkeeping is wrong, but I can’t see it. What is the bug here, and what’s the minimal fix?

function hasCycle(g, n, u = 0, seen = new Set()) {
  if (seen.has(u)) return false;
  seen.add(u);
  for (const v of g[u] || []) {
    if (seen.has(v)) return true;
    if (hasCycle(g, n, v, seen)) return true;
  }
  return false;
}

Sora

2

Your seen set is doing two jobs, so a node reached from one branch poisons later branches.

Hari