Detect Cycle in an Undirected Graph: DFS With Parent Tracking
Detect a cycle in an undirected graph with DFS and parent tracking — the intuition, a worked walkthrough, JavaScript code, and O(V+E) complexity analysis.
This article has an interactive companion
Don't just read it — step through it interactively, one state change at a time.
Cycle detection in an undirected graph looks like it should be as simple as "did I revisit a node I've already seen?" — but that naive rule fires on every edge and reports a cycle where none exists. The fix is one extra parameter carried through the recursion: the node you just came from. Get that one idea right and the whole problem collapses into a dozen lines of DFS.
This is the pattern behind union-find warmups, redundant-edge detection, and the "is this graph a tree?" question. It is worth internalizing the why, not just the code.
The problem
You are given an undirected graph with n nodes labeled 0 to n - 1 and a list of edges, where each edge [x, y] connects node x and node y. Return true if the graph contains at least one cycle, and false otherwise. A cycle is a path that starts and ends at the same node without reusing an edge.
Input: n = 3, edges = [[0, 1], [0, 2], [1, 2]]
Output: true // 0 - 1 - 2 - 0 closes a loop
Input: n = 3, edges = [[0, 1], [1, 2]]
Output: false // a straight line, no loopTwo facts about undirected graphs shape everything below:
- Every edge is bidirectional, so when you store an adjacency list, edge
[x, y]appears twice —yinx's list andxiny's list. - The graph may be disconnected (several separate pieces). A cycle in any piece counts, so you cannot just start from node
0and stop.
The brute force baseline
One correct-but-slow idea: an edge is part of a cycle exactly when its two endpoints are still connected after you delete it. If removing edge u - v leaves u and v reachable through some other path, that edge closed a loop.
function hasCycleBrute(n, edges) {
const reachableWithout = (from, to, skip) => {
const graph = Array.from({ length: n }, () => []);
edges.forEach(([x, y], idx) => {
if (idx === skip) return; // pretend this edge is gone
graph[x].push(y);
graph[y].push(x);
});
const stack = [from], seen = new Set([from]);
while (stack.length) {
const node = stack.pop();
if (node === to) return true;
for (const nb of graph[node]) {
if (!seen.has(nb)) { seen.add(nb); stack.push(nb); }
}
}
return false;
};
for (let e = 0; e < edges.length; e++) {
const [u, v] = edges[e];
if (reachableWithout(u, v, e)) return true;
}
return false;
}This is O(E · (V + E)): for each of the E edges you run a fresh traversal that costs O(V + E). On a dense graph that's cubic-ish and hopeless. It also rebuilds the graph every iteration. The right answer walks the graph once.
The key insight: a back-edge that isn't your parent
Run a DFS and mark nodes visited as you enter them. The temptation is to shout "cycle!" the instant you meet a visited neighbor. But in an undirected graph, the moment you step from curr into neighbor, neighbor's adjacency list contains curr right back — you'll immediately "revisit" the node you came from. That is not a cycle. It's the same edge, read backwards.
So carry the parent — the node you arrived from — into each recursive call. Then a visited neighbor means one of two things:
neighbor === parent→ that's just the edge you walked in on. Ignore it.neighbor !== parent→ a back-edge to an ancestor you already visited by a different route. That closes a loop. Cycle found.
That single comparison, neighbor !== parent, is the entire trick. Everything else is standard traversal.
The optimal solution
Build an adjacency list, keep a global visited set, and DFS from every unvisited node so disconnected components are all covered.
function hasCycle(n, edges) {
const graph = Array.from({ length: n }, () => []);
for (const [x, y] of edges) {
graph[x].push(y); // undirected: store both directions
graph[y].push(x);
}
const visited = new Set();
const dfs = (curr, parent) => {
visited.add(curr);
for (const neighbor of graph[curr]) {
if (!visited.has(neighbor)) {
if (dfs(neighbor, curr)) return true; // recurse; bubble up a cycle
} else if (neighbor !== parent) {
return true; // back-edge → cycle exists
}
}
return false;
};
for (let i = 0; i < n; i++) {
if (!visited.has(i) && dfs(i, -1)) return true; // -1 = no parent
}
return false;
}Two details worth pausing on. First, the recursion uses if (dfs(neighbor, curr)) return true — it only propagates a true. If a branch comes back false, the loop keeps checking the node's other neighbors instead of quitting early. Second, the outer loop launches a DFS from every node that no component has reached yet, with parent = -1 (a sentinel that no real node equals), so a cycle buried in a second disconnected piece is never missed.
Walkthrough
Trace n = 3, edges = [[0, 1], [0, 2], [1, 2]] — the triangle. The adjacency list is 0: [1, 2], 1: [0, 2], 2: [0, 1].
| Call | curr | parent | neighbor | visited | Action |
|---|---|---|---|---|---|
| dfs(0, -1) | 0 | -1 | — | {0} | mark 0 visited |
| 0 | -1 | 1 | {0} | 1 unvisited → recurse dfs(1, 0) | |
| dfs(1, 0) | 1 | 0 | — | {0, 1} | mark 1 visited |
| 1 | 0 | 0 | {0, 1} | 0 visited and 0 === parent → skip | |
| 1 | 0 | 2 | {0, 1} | 2 unvisited → recurse dfs(2, 1) | |
| dfs(2, 1) | 2 | 1 | — | {0, 1, 2} | mark 2 visited |
| 2 | 1 | 0 | {0, 1, 2} | 0 visited and 0 !== parent(1) → cycle! return true |
The true from dfs(2, 1) bubbles up through dfs(1, 0) and dfs(0, -1), and the function returns true. The decisive moment is the last row: node 2 sees node 0, which is visited but is not 2's parent (that's 1). That back-edge 2 - 0 is the third side of the triangle closing the loop. Swap the input to edges = [[0, 1], [1, 2]] and node 2 would only see its parent 1, so every neighbor gets skipped and the answer is false.
Complexity
| Approach | Time | Space | Why |
|---|---|---|---|
| Brute force (edge deletion) | O(E · (V + E)) | O(V + E) | one full traversal per edge |
| DFS + parent tracking | O(V + E) | O(V) | each node entered once, each edge scanned twice |
The DFS touches every node exactly once (the visited set guarantees it) and looks at every adjacency entry once — and there are 2E of those in an undirected graph — so the work is linear in V + E. Space is O(V) for the visited set plus the recursion stack, which can reach depth V on a long path.
Common mistakes
- Forgetting the parent check. Without
neighbor !== parent, the first edge you traverse instantly reports a false cycle, because the neighbor's list points straight back at you. This is the number-one bug in undirected cycle detection. - Returning
falsetoo eagerly. Writingreturn dfs(neighbor, curr)inside the loop returns whatever the first neighbor's subtree says, evenfalse, abandoning the remaining neighbors. Guard it:if (dfs(neighbor, curr)) return trueand let the loop continue otherwise. - Only starting from node 0. A disconnected graph can hide its cycle in a component that node
0never reaches. Loop over all nodes and DFS from each unvisited one. - Using
0as the "no parent" sentinel. Node0is a real node. Use-1(ornull) so the root's non-existent parent never accidentally matches a real neighbor. - Assuming the parent trick works for directed graphs. It does not. Directed cycle detection needs a recursion-stack / gray-node coloring instead, because direction removes the symmetric back-reference this whole approach relies on.
Where this pattern shows up next
DFS with per-node bookkeeping is the workhorse of graph problems. Once the visited-plus-context idea clicks, these follow naturally:
- Redundant Connection — the same "which edge closes the loop?" question, usually solved with union-find as the alternative to this DFS.
- Find if Path Exists in Graph — the reachability half of the brute-force baseline, standalone.
- All Paths From Source to Target — DFS that carries a running path instead of a parent.
- Max Area of Island — grid-flavored DFS where the bookkeeping counts cells instead of detecting loops.
You can also step through the detect-cycle DFS interactively and watch the call stack, the visited set, and the back-edge light up node by node.
FAQ
Why do you need to track the parent node in an undirected graph?
Because every undirected edge is stored in both directions. When DFS moves from curr to neighbor, that neighbor's adjacency list still contains curr, so a plain "have I visited this node?" check trips on the edge you just crossed and reports a cycle that isn't real. Passing the parent lets you distinguish the edge you came in on (neighbor === parent, harmless) from a genuine back-edge to a different ancestor (neighbor !== parent, a real cycle).
What is the time and space complexity of DFS cycle detection?
Time is O(V + E): the visited set ensures each of the V nodes is entered once, and the traversal scans each of the graph's 2E directed adjacency entries once. Space is O(V) — the visited set holds up to V nodes and the recursion stack can grow to depth V on a long chain. That's a huge improvement over the O(E · (V + E)) edge-deletion brute force.
How do you detect cycles in a disconnected graph?
Wrap the DFS in a loop that visits every node index. If a node hasn't been reached by any earlier component, launch a fresh DFS from it with parent = -1. Because the visited set is shared across all these launches, each component is explored exactly once, and a cycle in any component returns true immediately. Starting only from node 0 would silently miss cycles in every other piece.
Does this parent-tracking approach work for directed graphs?
No. In a directed graph an edge x → y does not imply y → x, so the symmetric back-reference that motivates the parent check never appears. Detecting cycles in a directed graph instead uses three-color marking (or a recursion-stack set): a node is "in progress" while its DFS subtree is unfinished, and re-encountering an in-progress node signals a cycle. The undirected neighbor !== parent rule would give wrong answers there.
Can you detect the cycle with union-find instead of DFS?
Yes, and it is often cleaner for the edge-list form of the input. Process edges one at a time, unioning the two endpoints; if an edge's endpoints already share a root, adding it would connect two already-connected nodes and therefore close a cycle. That runs in near-linear O(E · α(V)) time. DFS is the natural choice when you already hold an adjacency list or also need the traversal order; union-find shines when edges arrive as a stream, which is exactly the setup in Redundant Connection.
Make it stick: run this one yourself
Don't just read it — step through it interactively, one state change at a time.