Cycle detection in undirected graphs comes down to a few key questions: how do you avoid false positives from traversing an edge you came from, how do you handle disconnected components, and what changes when you use Union-Find instead of DFS?

This chapter covers three approaches to detect cycles in an undirected graph: DFS with parent tracking, Union-Find, and BFS with parent tracking.

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.

The textbook definition above assumes a simple graph (no self-loops, no parallel edges). Real inputs sometimes include these, and they change what counts as a cycle and which algorithms still work.

Self-Loops

A self-loop is an edge from a vertex to itself, like v - v. By any reasonable definition, that is a cycle of length 1. Detecting it is trivial: while iterating edges (Union-Find) or while iterating a vertex's adjacency list (DFS/BFS), check whether u == v. If yes, you have a cycle without doing any traversal.

DFS with parent tracking will also flag a self-loop correctly. When you reach v and scan its neighbors, you encounter v itself; v is visited, and the parent of v is some other vertex (or -1 for the root), so neighbor == parent is false, and the algorithm reports a cycle.

Parallel Edges (Multi-Edges)

A multi-edge is two or more distinct edges between the same pair of vertices. Two parallel edges between A and B form a cycle of length 2 (go A → B on one edge, B → A on the other).

DFS with parent tracking fails on multi-edges. The standard parent-skip rule says "ignore the neighbor that equals the parent, because that is the edge you just traversed." With multi-edges, both copies of the edge to the parent satisfy neighbor == parent, so the algorithm skips both and never reports the cycle.

There are two ways to fix this:

If your input is guaranteed to be a simple graph (the usual assumption in interview problems), neither edge case matters. If the input could contain self-loops or parallel edges, prefer Union-Find or switch DFS to edge-ID tracking.

DFS is the most direct way to detect cycles in an undirected graph.

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. 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.

To handle disconnected components, run DFS from every unvisited vertex.

Implementation

Complexity

Union-Find takes a different approach. Instead of traversing the graph, it processes edges one at a time and checks whether the two endpoints are 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.

Union-Find reduces cycle detection to a membership query.

Implementation (with Path Compression and Union by Rank)

Path compression and union by rank bring the amortized cost of each operation down to nearly O(1). Path compression flattens the tree by pointing each node directly at the root during a find, and union by rank attaches the shorter tree under the taller one to keep trees shallow.

Complexity

The BFS approach works on the same principle as DFS with parent tracking, 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.