Detect Cycle in Undirected Graph: Beginner’s Guide with DFS, BFS and Union Find

One of the most important problems in graph algorithms is to detect cycle in undirected graph. It appears in coding interviews, university DSA exams, and competitive programming almost every week. If you are just starting with graphs, this topic can look intimidating. But once you understand what a cycle is and learn the parent tracking trick, the solution becomes very clear.

This guide covers everything a beginner needs. What a graph is, what a cycle means, what a back edge is, and how to detect cycles using three methods: DFS, BFS, and Union Find. No code. Just clear concepts, visual tables, and step by step walkthroughs.

Quick Answer

To detect cycle in an undirected graph, use DFS or BFS while tracking visited nodes and their parent. If you reach a node that is already visited and it is not the parent of the current node, a cycle exists. You can also use Union Find: if two nodes of an edge already belong to the same group, a cycle is found.

What Is a Graph

A graph is a collection of nodes connected by edges.

• Node (Vertex): A point in the graph. Example: a city on a map.
• Edge: A connection between two nodes. Example: a road between two cities.
• Adjacency List: The most common way to store a graph. Each node keeps a list of its connected neighbors.

What Is an Undirected Graph

In an undirected graph, every edge goes both ways. If there is an edge between node A and node B, you can travel from A to B and also from B to A. There is no fixed direction.

This blog covers undirected graphs only. The method to detect cycle in a directed graph is different and uses a separate approach.

Master graph algorithms, DFS, BFS, recursion, trees, heaps, hashing, dynamic programming, and advanced problem-solving techniques with HCL GUVI’s DSA for Programmers course. Build strong coding and interview skills through hands-on exercises, real-world examples, and industry-focused learning designed for beginners and aspiring software developers. 

What Is a Cyclic and Acyclic Graph

• Cyclic Graph: A graph that contains at least one cycle. If you can start at a node, travel through edges, and come back to the same node, the graph is cyclic.
• Acyclic Graph: A graph with no cycles at all. You cannot return to any node once you leave it.

A connected acyclic undirected graph is called a tree. This is an important connection. If you detect no cycle in a connected undirected graph, it is a valid tree.

What Is a Cycle in an Undirected Graph

A cycle means you start at a node, follow a series of edges, and arrive back at the same starting node without retracing the exact same edge.

Example with a cycle:

Nodes: 0, 1, 2. Edges: 0-1, 1-2, 2-0

Path: 0 to 1 to 2 to 0. You came back to where you started. Cycle exists.

Example without a cycle:

Nodes: 0, 1, 2. Edges: 0-1, 1-2

Path: 0 to 1 to 2. No way to return to 0. No cycle.

What Is a Back Edge

A back edge is a key concept used when you detect cycle in undirected graph using DFS. During a DFS traversal, the algorithm builds a tree of visited nodes. A back edge is an edge that connects a current node to a node that was already visited earlier in the traversal and is not its direct parent.

• Tree edge: An edge that connects a node to an unvisited neighbor. Normal DFS movement.
• Back edge: An edge that connects a node to an already visited non-parent node. This signals a cycle.

A graph has a cycle if and only if a back edge exists during DFS. This is the core idea behind the DFS method.

Why Parent Tracking Is Important

In an undirected graph, every edge appears in both directions. If you travel from node 0 to node 1, node 1 will also list node 0 as a neighbor. Without tracking the parent, your algorithm would see node 0 as already visited when checking from node 1 and falsely report a cycle.

The rule is simple: if you visit a neighbor that is already visited AND it is not the direct parent of the current node, you have found a back edge and a cycle exists.

Method 1: Detect Cycle in Undirected Graph Using DFS

DFS stands for Depth First Search. It explores as far as possible along one path before backtracking. Think of it like walking through a maze by always going forward until you hit a dead end, then stepping back.

How DFS Cycle Detection Works

• Start from any unvisited node
• Mark it visited and record its parent
• Visit each neighbor one by one
• If a neighbor is already visited and is not the parent, a back edge is found and a cycle exists
• If a neighbor is not visited, move into it and repeat the process

Step-by-Step DFS Walkthrough

Graph: 4 nodes. Edges: 0-1, 1-2, 2-0, 0-3

At step 4, node 0 is already visited and is not the parent of node 2. Back edge found. Cycle detected.

DFS at a Glance

• What it uses: Visited array and parent tracking
• How it moves: Deep into the graph first, then backtracks
• Cycle signal: A visited neighbor that is not the parent (back edge)
• Time Complexity: O(V + E) where V is nodes and E is edges
• Space Complexity: O(V)

Method 2: Detect Cycle in Undirected Graph Using BFS

BFS stands for Breadth First Search. Instead of going deep, it explores all neighbors of a node before moving further. It uses a queue to process nodes level by level. The cycle detection logic is the same as DFS but implemented iteratively.

How BFS Cycle Detection Works

• Add the starting node and its parent (use -1 for the first node since it has no parent) into a queue
• Mark it visited
• For each node taken out of the queue, check all its neighbors
• If a neighbor is not visited, mark it visited and add it to the queue with the current node as its parent
• If a neighbor is already visited and is not the parent of the current node, a cycle is found

Step-by-Step BFS Walkthrough

Graph: Same as above. Edges: 0-1, 1-2, 2-0, 0-3

At step 3, node 2 is already visited when checked from node 1, and node 2 is not the parent of node 1. Cycle detected.

BFS at a Glance

• What it uses: A queue storing node and parent pairs, and a visited array
• How it moves: Level by level, all neighbors first
• Cycle signal: A visited neighbor that is not the parent
• Time Complexity: O(V + E)
• Space Complexity: O(V)

Method 3: Detect Cycle in Undirected Graph Using Union Find

Union Find (also called Disjoint Set Union or DSU) is a completely different approach. It does not traverse the graph. Instead, it groups nodes into connected components and checks whether adding a new edge connects two nodes that are already in the same group.

Key Terms in Union Find

• Find: Returns which group a node belongs to
• Union: Merges two groups into one
• Path Compression: A technique that makes future Find operations faster by flattening the group structure
• Cycle Rule: If both nodes of an edge already belong to the same group before connecting them, adding that edge creates a cycle

How Union Find Cycle Detection Works

• Give every node its own group at the start
• For each edge between node u and node v, find the group of u and the group of v
• If both are in the same group, a cycle is detected
• If they are in different groups, merge them and move to the next edge

Step-by-Step Union Find Walkthrough

Graph: 3 nodes. Edges: 0-1, 1-2, 2-0

Union Find at a Glance

• What it uses: A parent array tracking which group each node belongs to
• How it works: Merges groups for each edge, flags cycle if both nodes share a group
• Cycle signal: Both nodes of an edge are already in the same group
• Time Complexity: Nearly O(E) with path compression
• Space Complexity: O(V)

Comparison of All Three Methods to Detect Cycle in Undirected Graph

Cyclic vs Acyclic: Key Differences

Where Is Detect Cycle in Undirected Graph Used in Real Life

• Deadlock detection: Operating systems check for cycles in resource allocation graphs to find processes stuck waiting on each other indefinitely
• Network routing: Routers detect cycles to stop data packets from looping endlessly across a network
• Dependency management: Package managers like npm check for circular dependencies between libraries before installation
• Circuit design: Electronics tools verify that circuits do not have unintended closed loops that could cause short circuits
• Minimum Spanning Tree: Kruskal’s algorithm uses Union Find cycle detection to build the minimum spanning tree without adding any redundant edge

Tips for Beginners Learning to Detect Cycle in Undirected Graph

• Always track the parent node. Without it, every edge in an undirected graph looks like a cycle because it appears in both directions. This is the single most important thing to remember.
• Handle disconnected graphs. Always loop through all nodes and run DFS or BFS from every unvisited node. A cycle could be hiding in any disconnected component.
• Union Find is best for edge list inputs. If your problem gives you a list of edges rather than an adjacency list, Union Find is often the cleanest and fastest choice.
• Start with DFS. It is the most expected solution in interviews and the easiest to explain step by step with back edge reasoning.
• Draw the graph on paper first. Before solving anything, sketch the nodes and edges and trace through the algorithm manually. Visual tracing removes most confusion immediately.

Remember: no cycle means it is a tree. If you are asked to check whether a graph is a valid tree, you are essentially being asked to detect cycle in undirected graph and confirm connectivity.

Conclusion

Learning to detect cycle in undirected graph is not just about passing one exam question. It is the gateway to Kruskal’s algorithm, topological sort, strongly connected components, and many other advanced graph topics that show up repeatedly in interviews.

Start by tracing through the DFS walkthrough on paper with your own small graph. Once DFS feels natural, trace through BFS. Then walk through Union Find and notice how completely differently it approaches the same problem. Understanding all three methods makes you versatile, and that versatility is exactly what interviewers test.

The concept is simple once you see it clearly: track where you have been, remember where you came from, and if you ever see a familiar face that is not the one who sent you, you have found your cycle.

FAQs

1. What does it mean to detect cycle in undirected graph?

It means checking whether there is any path in the graph that starts from a node, travels through a series of connected edges, and returns to the same starting node without reusing the same edge. If such a path exists, the graph has a cycle.

2. Why do we track the parent node when we detect cycle in undirected graph? 

In an undirected graph, every edge goes both ways. Without tracking the parent, the algorithm mistakes the reverse edge (going back the way you came) as a cycle. Tracking the parent lets you skip that reverse edge and only flag genuine cycles.

3. What is a back edge and why does it matter for cycle detection?

A back edge is an edge that connects the current node to an already visited node that is not its parent in the DFS tree. Finding a back edge means a cycle exists. No back edge means no cycle. This is the fundamental reason DFS works for cycle detection.

4. What is Union Find and when should I use it to detect cycle in undirected graph?

Union Find groups nodes into connected components. If two nodes of an edge are already in the same group before you connect them, adding that edge creates a cycle. Use Union Find when your input is an edge list or when you are solving problems like Kruskal’s MST or LeetCode 684.

5. Does this approach to detect cycle in undirected graph work on disconnected graphs?

Yes. You need to run DFS or BFS from every unvisited node, not just one. A disconnected graph has separate components and a cycle might exist in any one of them. Always loop through all nodes to cover every component.