How Do You Detect a Cycle in an Undirected Graph?
Learn DFS parent-tracking and Union-Find techniques to detect cycles in an undirected graph, with complexity and code.
Expected Interview Answer
You detect a cycle in an undirected graph with DFS (or BFS) that tracks each node's immediate parent, and a cycle exists if you reach an already-visited neighbor that is not the node you just came from — alternatively, Union-Find flags a cycle whenever an edge connects two vertices already in the same set.
In DFS, every edge to an already-visited vertex would look like a cycle, except the edge straight back to the parent you just arrived from, which is expected in an undirected graph since every edge is bidirectional. So the check must explicitly exclude that parent edge; any other already-visited neighbor confirms a true cycle. The Union-Find (disjoint set) approach is often cleaner: process edges one at a time, and if the two endpoints already share the same root, adding this edge would close a cycle, so skip it (this is also exactly how Kruskal's minimum spanning tree algorithm avoids cycles). Both approaches run close to O(V + E) — DFS exactly, Union-Find near-linear with path compression and union by rank.
- DFS approach runs in O(V + E) time
- Union-Find approach runs in near-linear time with path compression
- Directly reused by Kruskal's MST algorithm to reject cycle-forming edges
- Simple parent-exclusion rule avoids false positives from bidirectional edges
AI Mentor Explanation
A scorer tracing a chain of “fielded the ball from” hand-offs during a relay throw walks player to player, and every hand-off naturally looks two-way since the ball could have gone either direction between two players. Reaching a player you just received the ball from is expected and not a problem, since that is simply the same hand-off in reverse. But reaching any other player who already touched the ball earlier in this relay means the ball path looped back on itself, forming a genuine cycle in the fielding chain. Excluding only the immediate previous player, and nothing else, is exactly the parent-exclusion rule undirected cycle detection relies on.
Step-by-Step Explanation
Step 1
DFS with parent tracking
Walk the graph via DFS, passing along the parent vertex you arrived from.
Step 2
Skip the parent edge
When checking a neighbor, ignore it if it is exactly the parent vertex — that edge is expected.
Step 3
Flag any other visited neighbor
If a neighbor is visited and is not the parent, a cycle exists.
Step 4
Or use Union-Find per edge
For each edge (u, v), if find(u) == find(v) already, adding it creates a cycle; otherwise union them.
What Interviewer Expects
- Explain why the parent edge must be explicitly excluded in undirected DFS
- Present the Union-Find alternative and connect it to Kruskal's MST algorithm
- State time complexity for both approaches
- Handle disconnected graphs by checking every component
Common Mistakes
- Forgetting to exclude the parent edge, causing every edge to be falsely flagged as a cycle
- Applying the directed-graph three-color technique to an undirected graph unnecessarily
- Using Union-Find without path compression, degrading performance on large graphs
- Not checking all connected components in a disconnected graph
Best Answer (HR Friendly)
“In an undirected graph, I detect a cycle by walking the graph and remembering which node I just came from. If I ever reach a node I have already visited that is not the one I just came from, that means there is a loop. I also like the Union-Find approach, where a cycle shows up the moment an edge connects two nodes that are already in the same group.”
Code Example
def has_cycle(graph):
visited = set()
def dfs(node, parent):
visited.add(node)
for neighbor in graph[node]:
if neighbor not in visited:
if dfs(neighbor, node):
return True
elif neighbor != parent:
return True
return False
return any(n not in visited and dfs(n, None) for n in graph)Follow-up Questions
- How would you solve this using Union-Find instead of DFS?
- How does undirected cycle detection differ from the directed-graph version?
- How would you find and print the actual cycle path, not just detect one?
- How does this relate to Kruskal's minimum spanning tree algorithm?
MCQ Practice
1. In undirected DFS cycle detection, why must the parent vertex be excluded?
Every undirected edge is bidirectional, so the edge back to the immediate parent is always revisited and must be excluded.
2. In the Union-Find approach to cycle detection, when is a cycle detected?
If both endpoints of an edge already belong to the same set, adding that edge would close a loop.
3. Which classic algorithm reuses the Union-Find cycle check to build a minimum spanning tree?
Kruskal's algorithm adds edges in increasing weight order and uses Union-Find to skip any edge that would form a cycle.
Flash Cards
What must undirected DFS cycle detection explicitly exclude? — The edge back to the immediate parent vertex.
What is the Union-Find rule for detecting a cycle? — An edge whose two endpoints already share the same root would form a cycle.
What algorithm reuses Union-Find cycle detection? — Kruskal's minimum spanning tree algorithm.
What is the time complexity of the DFS approach to undirected cycle detection? — O(V + E).