Detect cycle in an undirected graph using BFS

Learn how to detect a cycle in an undirected graph with a breadth-first search (BFS) approach. This beginner-friendly guide walks you through the code, adds helpful comments, and explains each step in plain English.

What the Problem Asks

GFG “Detect Cycle in an Undirected Graph”
You’re given an undirected graph with V vertices (numbered 0 to V-1) and a list of edges. Determine whether the graph contains at least one cycle.

• Input:
  • V: number of vertices
  • edges: list of pairs [u, v], each an undirected edge between u and v
• Output:
  • True if there is a cycle, False otherwise

Intuition & Approach

Why BFS?

• We start from each unvisited node and do a BFS.
• We track the “parent” of each node so we don’t mistake the bidirectional edge back to the parent for a cycle.

Detecting a Cycle:

• When we see a neighbor that’s already visited but is not the parent, we know there’s another path back to it → a cycle.

Multiple Components:

• The graph may be disconnected, so we repeat BFS from every unvisited vertex.

Code

from collections import deque

class Solution:
    def isCycle(self, V, edges):
        # 1. Build adjacency list
        adj_list = [[] for _ in range(V)]
        for u, v in edges:
            adj_list[u].append(v)
            adj_list[v].append(u)

        visited = [0] * V  # 0 = unvisited, 1 = visited

        # 2. For each vertex, if unvisited, start BFS
        for i in range(V):
            if visited[i] == 1:
                continue

            queue = deque()
            queue.append((i, -1))  # (node, parent)
            visited[i] = 1

            # 3. Standard BFS loop
            while queue:
                node, parent = queue.popleft()
                # 4. Check all neighbors
                for adjNode in adj_list[node]:
                    if visited[adjNode] == 0:
                        visited[adjNode] = 1
                        queue.append((adjNode, node))
                    else:
                        # If visited and not the parent, it's a cycle
                        if adjNode != parent:
                            return True

        # 5. No cycle found
        return False

Step-by-Step Explanation

• Build adjacency list so we can quickly look up neighbors of any node.
• Visited array keeps track of nodes we’ve enqueued.
• Outer loop: ensures we handle disconnected parts of the graph by starting BFS at any unvisited vertex.
• Queue entries store (current_node, parent_node).
• When visiting each neighbor:
  • If it’s unvisited, mark it and enqueue with its parent.
  • If it’s visited and not the parent, we’ve found a back-edge → a cycle.
• Return True immediately on cycle detection; otherwise False at the end.

Time & Space Complexity

• Time Complexity: O(V + 2E)
  • Each vertex and edge is processed at most once in BFS.
• Space Complexity: O(V + 2E)
  • Adjacency list uses O(V+E), queue and visited array use O(V).

Conclusion

This BFS-based cycle detection is simple and runs in linear time. By tracking the parent of each node, you avoid false positives from the undirected nature of the graph. Once you’ve got this pattern down, you can adapt it to many graph problems that need cycle detection or reachability checks. Happy coding!

For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.