I’m checking whether a directed graph has a cycle, but this function returns false for some graphs that clearly have one. I think my visited bookkeeping is wrong, but I can’t spot it.
function hasCycle(graph) {
const visited = new Set();
const stack = new Set();
function dfs(node) {
if (visited.has(node)) return false;
visited.add(node); stack.add(node);
for (const nei of graph[node] || []) {
if (stack.has(nei)) return true;
if (dfs(nei)) return true;
}
stack.delete(node); return false;
}
return Object.keys(graph).some(dfs);
}
What case is this logic skipping, and what’s the minimal fix?
@ArthurDent the miss is when DFS reaches a node that was already marked visited, so it exits before considering whether that node is part of the current recursion path. In directed-cycle detection, the recursion-stack check has to win first.
function hasCycle(graph) {
const visited = new Set();
const stack = new Set();
function dfs(node) {
if (stack.has(node)) return true;
if (visited.has(node)) return false;
visited.add(node);
stack.add(node);
for (const nei of graph[node] || []) {
if (dfs(nei)) return true;
}
stack.delete(node);
return false;
}
return Object.keys(graph).some(dfs);
}
That’s the minimal fix: check stack before visited, and then you can fold the neighbor stack.has(nei) case into dfs(nei) cleanly.
@ArthurDent Your cycle check is currently treating “already seen” as “definitely safe,” not “possibly still active on this DFS path.”
2. Conceptual Explanation
The missed case is a back-edge to a node that is still in the current recursion stack. In directed graphs, that active-path revisit is the actual cycle signal. visited only tells you the node was seen before, but stack tells you it is active right now. So the stack check has to run first.
3. Minimal Fix```js
function hasCycle(graph) {
const visited = new Set();
const stack = new Set();
function dfs(node) {
if (stack.has(node)) return true;
if (visited.has(node)) return false;
visited.add(node);
stack.add(node);
for (const nei of graph[node] || []) {
if (dfs(nei)) return true;
}
stack.delete(node);
return false;
}
return Object.keys(graph).some(dfs);
}
- `stack.has(node)` detects a back-edge into the current DFS path.
- `visited.has(node)` skips nodes that are already fully processed.
- This prevents real cycles from being discarded as harmless revisits.
## 5. Sanity Check```js
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
```## 6. Optional Practical Tip
If you prefer, use node states (`unseen`, `visiting`, `done`) instead of two sets.
BayMax
Your DFS is currently treating a node that is still active in the current path as merely “already seen,” not “part of a cycle.”
The skipped case is a back-edge into the current recursion chain, like B -> C -> B. visited only tells you a node was reached before; it does not tell you whether that node is still being explored right now. For directed cycle detection, the active-path check has to happen first.
Minimal Fix
function hasCycle(graph) {
const visited = new Set();
const stack = new Set();
function dfs(node) {
if (stack.has(node)) return true;
if (visited.has(node)) return false;
visited.add(node);
stack.add(node);
for (const nei of graph[node] || []) {
if (dfs(nei)) return true;
}
stack.delete(node);
return false;
}
return Object.keys(graph).some(dfs);
}
Your DFS is currently doing “skip any node seen before,” not “distinguish nodes on the current path from nodes fully processed.”
In directed cycle detection, visited and stack have different jobs. A cycle exists when you re-enter a node that is still on the current DFS path. If you check visited before stack at the top of dfs, you can classify an active-path node as merely “already seen” and miss the cycle.
The smallest fix is this:
function hasCycle(graph) {
const visited = new Set();
const stack = new Set();
function dfs(node) {
if (stack.has(node)) return true;
if (visited.has(node)) return false;
visited.add(node);
stack.add(node);
for (const nei of graph[node] || []) {
if (dfs(nei)) return true;
}
stack.delete(node);
return false;
}
return Object.keys(graph).some(dfs);
}
stack.has(node) detects a back-edge into the current recursion path.
visited.has(node) skips nodes that were already fully explored.
This prevents active-path nodes from being treated like harmless previously processed nodes.
Quick check:
function hasCycle(graph) {
const visited = new Set();
const stack = new Set();
function dfs(node) {
if (stack.has(node)) return true;
if (visited.has(node)) return false;
visited.add(node);
stack.add(node);
for (const nei of graph[node] || []) {
if (dfs(nei)) return true;
}
stack.delete(node);
return false;
}
return Object.keys(graph).some(dfs);
}
console.log(hasCycle({ A: ["B"], B: ["C"], C: ["A"] })); // true
console.log(hasCycle({ A: ["B"], B: ["C"], C: [] })); // false
console.log(hasCycle({ A: ["B"], B: ["D"], D: ["B"] })); // true
One practical caveat: if a node appears only in neighbor lists and not as a key, include it in your outer start-node set.
Your DFS is currently treating “seen before” as “safe,” not “currently active on this recursion path.”
In directed graphs, that distinction matters: revisiting a node in the active path is exactly what a cycle is. If the active-path check does not happen first, you can miss real cycles.
The smallest fix is this:
function hasCycle(graph) {
const visited = new Set();
const stack = new Set();
function dfs(node) {
if (stack.has(node)) return true;
if (visited.has(node)) return false;
visited.add(node);
stack.add(node);
for (const nei of graph[node] || []) {
if (dfs(nei)) return true;
}
stack.delete(node);
return false;
}
return Object.keys(graph).some(dfs);
}
A few details make this reliable in practice:
stack.has(node) catches a back-edge into the current DFS chain.
visited.has(node) skips nodes that are already fully processed.
This prevents active-path nodes from being misclassified as harmless repeats.
If you run it on a couple of small graphs, the behavior is clearer:
