Detect Cycle in an Undirected Graph Using BFS

The problem is to detect whether a cycle exists in an undirected graph using the Breadth-First Search (BFS) traversal technique.

A cycle in an undirected graph occurs when there is a path that starts and ends at the same node without reusing any edge.

This problem is important in applications like deadlock detection, circuit analysis, and validating graph structures.

Understanding the Problem

We are given an undirected graph, and our task is to determine whether the graph contains a cycle using Breadth-First Search (BFS).

In an undirected graph, a cycle is a path that starts and ends at the same vertex without repeating any edge, and at least one vertex is visited more than once through a path other than its direct parent.

We must be careful to not falsely detect a cycle just because a node connects back to its parent (which is allowed in an undirected graph). The key is to detect a back-edge to a previously visited node that is not the direct parent.

Step-by-Step Solution with Example

Step 1: Represent the Graph

We’ll use an adjacency list to represent the graph. For example, consider the graph:

0 - 1
|   |
3 - 2

This graph forms a cycle: 0 → 1 → 2 → 3 → 0.

We can represent this as: { 0: [1, 3], 1: [0, 2], 2: [1, 3], 3: [0, 2] }

Step 2: Use a Visited Array

We'll keep a visited array to mark the nodes we’ve already seen to avoid revisiting them unnecessarily.

Step 3: Start BFS from Each Unvisited Node

Since the graph may be disconnected, we’ll start BFS from each unvisited node to ensure we check every component.

Step 4: BFS with Parent Tracking

In the BFS traversal, for each node, we’ll track its parent. If we encounter a neighbor that has already been visited and is not the parent, we’ve detected a cycle.

Step 5: Return the Result

If any BFS detects a cycle, return true. If none do, return false.

JavaScript-like Pseudocode

function isCyclic(graph) {
  let visited = new Set();

  for (let node in graph) {
    if (!visited.has(node)) {
      if (bfsCycleCheck(graph, node, visited)) {
        return true;
      }
    }
  }

  return false;
}

function bfsCycleCheck(graph, start, visited) {
  let queue = [[start, -1]];
  visited.add(start);

  while (queue.length) {
    let [node, parent] = queue.shift();
    for (let neighbor of graph[node]) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        queue.push([neighbor, node]);
      } else if (neighbor != parent) {
        return true; // cycle detected
      }
    }
  }

  return false;
}

Edge Cases

Case 1: Graph with No Cycles

If the graph is a tree (no cycles), BFS will never encounter a visited node except its parent. So the check if neighbor is visited and neighbor ≠ parent never passes, and we correctly return false.

Case 2: Graph with a Cycle

When there is a cycle, BFS will eventually reach a visited node that is not its parent — a back-edge — confirming a cycle. We return true immediately.

Case 3: Disconnected Graph

If the graph has multiple disconnected components, we check each one. If any component has a cycle, we return true. Otherwise, we return false after checking all.

Case 4: Empty Graph

If the graph is empty (no nodes), there’s nothing to explore and no cycle to detect. The function returns false.

Finally

Cycle detection in an undirected graph using BFS is an intuitive approach for beginners. The key takeaway is understanding the difference between revisiting a parent (which is okay) and finding a back-edge (which signals a cycle). With careful tracking of visited nodes and parent information, BFS provides a clean and structured way to detect cycles even in disconnected graphs.

1. Initialize a visited set.
2. Loop over each node in the graph:
1. If the node is not visited, initiate BFS from that node.
2. Use a queue to store [current, parent] pairs.
3. While the queue is not empty:
1. Dequeue a pair [node, parent].
2. For every neighbor of node:
• If neighbor is not visited, add [neighbor, node] to queue.
• If neighbor is visited and not equal to parent → Cycle detected.
3. If no such condition occurs, return false (no cycle).

O(V)

Explanation: The queue and visited set both store up to O(V) elements, where V is the number of vertices in the graph.