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

**URL:** <https://forum.kirupa.com/t/why-does-this-dfs-cycle-check-miss-a-loop-in-a-directed-graph/680082>\
**Category:** web dev\
**Created:** [April 6, 2026, 6:00am UTC](https://forum.kirupa.com/t/why-does-this-dfs-cycle-check-miss-a-loop-in-a-directed-graph/680082 "2026-04-06T06:00:10Z")\
**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 6, 2026, 6:00am UTC](https://forum.kirupa.com/t/why-does-this-dfs-cycle-check-miss-a-loop-in-a-directed-graph/680082/1 "2026-04-06T06:00:10Z")

</div>

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.

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

---

<div class="post-metadata">

**Author:** ![Yoshiii](https://yyz1.discourse-cdn.com/flex011/user_avatar/forum.kirupa.com/yoshiii/32/31156_2.png) [@Yoshiii](https://forum.kirupa.com/u/Yoshiii)\
**Post date:** [April 6, 2026, 6:14am UTC](https://forum.kirupa.com/t/why-does-this-dfs-cycle-check-miss-a-loop-in-a-directed-graph/680082/2 "2026-04-06T06:14:30Z")

</div>

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:

```js
if (path.has(node)) return true;
if (visited.has(node)) return false;
```

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

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