Cycle detection in undirected graphs is one of those problems that sounds simple on paper but trips up a surprising number of interview candidates. The core idea is straightforward, but the details matter: how do you avoid false positives from traversing an edge you just came from? How do you handle disconnected components? What changes when you use Union-Find instead of DFS?

By the end of this chapter, you will know three different ways to detect cycles in an undirected graph. Let us dive in.

A cycle in an undirected graph is a path that starts at some vertex, travels through one or more other vertices (each connected by edges), and returns to the starting vertex without repeating any edge.

More precisely, a cycle is a sequence of vertices v0, v1, v2, ..., vk where:

That third point is important. In an undirected graph, going from A to B and immediately back to A does not count as a cycle. That is just traversing the same edge twice. A real cycle requires at least three vertices forming a closed loop.

Here is a graph that contains a cycle:

In this graph, B - C - D - B forms a cycle. The vertices B, C, and D create a closed loop. Meanwhile, vertex E is connected to A but is not part of any cycle.

And here is a graph with no cycle (a tree):

No matter which vertex you start from, there is exactly one path to every other vertex. No closed loops, no cycles. This is what makes it a tree.

Cycle detection is not just an academic exercise. It shows up in real systems and real interviews for several important reasons.

Checking if a Graph is a Tree

A graph is a valid tree if and only if it is connected and has no cycles. This is one of the most common interview problems involving cycle detection. You cannot verify that a graph is a tree without checking for cycles.

Network Reliability

In computer networks, cycles can cause broadcast storms where packets loop forever. Spanning tree protocols (like STP) detect and break cycles to prevent this. Understanding cycle detection helps you understand how production networks actually work.

Deadlock Detection

In operating systems, resource allocation graphs can have cycles. A cycle means a set of processes are all waiting for each other, and none can proceed. Detecting this cycle is how the OS identifies deadlocks.

Redundant Connection Detection

In problems like "find the edge that, if removed, makes the graph a tree," you need to find exactly which edge is completing a cycle. Union-Find is perfect for this.

Graph Validity

Many algorithms assume the input graph has certain properties (no cycles, connected, etc.). Cycle detection is a preprocessing step to validate these assumptions before running more complex algorithms.

DFS is the most intuitive way to detect cycles, and it is usually the first approach interviewers expect you to know.

The Core Idea

When you run DFS on an undirected graph, you explore as deep as possible along each branch before backtracking. You mark vertices as visited so you do not process them again. Now here is the key insight: if during DFS you encounter a neighbor that is already visited, AND that neighbor is not the vertex you just came from (the parent), then you have found a cycle.

Why do we need the parent check? Because in an undirected graph, every edge goes both ways. When you travel from vertex A to vertex B, vertex B's adjacency list includes A. If you do not track the parent, you would see A as "already visited" and incorrectly report a cycle.

In this diagram, we are at B (current vertex). A is the parent (we came from A). C is visited but is NOT the parent. This means there is another path from B to C that does not go through the edge we are currently on. That means there is a cycle.

How It Works Step by Step

Implementation

Complexity

Union-Find takes a completely different angle. Instead of traversing the graph, it processes edges one at a time and asks a simple question: "Are these two vertices already connected?"

The Core Idea

Start with every vertex in its own set. For each edge (u, v), check if u and v belong to the same set.

That is it. The elegance of Union-Find is that it reduces cycle detection to a membership query.

How It Works Step by Step

Implementation (with Path Compression and Union by Rank)

Why Path Compression and Union by Rank?

Without optimizations, find() can take O(V) in the worst case (a long chain). Path compression flattens the tree during find operations, making future lookups faster. Union by rank ensures we always attach the shorter tree under the taller one, keeping the tree balanced. Together, these two optimizations bring the amortized time per operation down to nearly O(1), specifically O(alpha(V)) where alpha is the inverse Ackermann function, which is effectively constant for any practical input size.

Complexity

The BFS approach works on the same principle as DFS with parent tracking, just using a queue instead of recursion. If during BFS we encounter a visited neighbor that is not the parent of the current vertex, we have found a cycle.

Implementation

BFS has the same time and space complexity as DFS: O(V + E) time and O(V) space. The main practical difference is that BFS uses an explicit queue and avoids recursion, which can be helpful if the graph is very deep and you are worried about stack overflow.

For most interview problems, DFS is the default choice. Use Union-Find when the problem gives you an edge list, asks you to find the specific edge causing the cycle, or involves incrementally adding edges.

Let us trace the DFS approach on a concrete graph. Consider this graph with 6 vertices and 7 edges:

Edges: (0,1), (1,2), (2,3), (3,4), (4,2), (0,5)

The cycle here is 2 - 3 - 4 - 2. Let us trace DFS with parent tracking.

The moment we are at vertex 4 and see that neighbor 2 is visited but is NOT our parent (our parent is 3), we know there is another path from 4 to 2. That path goes 4 -> 3 -> 2, and the edge 4 -> 2 creates a second path. Two distinct paths between the same vertices means a cycle.

Now let us also trace the Union-Find approach on the same graph.

When we process edge (4,2), both vertices already belong to the same set (their root is 0). This means they are already connected, so adding this edge creates a cycle.