G-11: Detect a Cycle in an Undirected Graph using BFS

Detecting cycles in an undirected graph is a fundamental graph problem with widespread applications in deadlock detection, network routing, and dependency resolution. This chapter explores how to leverage Breadth-First Search (BFS) alongside a parent-tracking mechanism to determine whether an undirected graph contains a cycle.

1. Why Do We Need Cycle Detection?

In many real-world systems, graphs are used to represent relationships, dependencies, or pathways.

• Deadlock Detection: In operating systems, resource allocation graphs must be checked for cycles to prevent processes from locking each other indefinitely.
• Network Routing: Unintended loops in network topologies can cause broadcast storms or endless packet circulation.
• Dependency Graphs: Knowing whether circular dependencies exist prevents infinite build loops or invalid execution states.

2. Core Mental Model & Real-Life Analogy

Real-Life Analogy: Exploring a Maze with Walkie-Talkies

Imagine you and a friend enter a maze (graph) from the same entrance. You split up, exploring different corridors (paths) at the same walking speed (levels in BFS).

• If you each walk down separate corridors and eventually bump into each other at the exact same dead-end room from opposite sides, you immediately realize: "Wait a minute! There is a loop (cycle) in this maze!"
• However, if you simply walk down a corridor and immediately turn back to the person who just handed you a flashlight, that is just your starting point—not a cycle.

In graph theory, a cycle occurs if during traversal, you encounter an adjacent node that is already visited and is not the direct parent you just came from.

3. BFS Traversal vs. Cycle Detection BFS

Standard BFS explores a graph level by level, utilizing a queue and a visited array.

Level 0:        [1]
                 |
Level 1:      /     \
            [2]     [3]
             |     /   \
Level 2:    [5]  [6]   [4]
             |
Level 3:    [7]

To adapt BFS for cycle detection, standard traversal is insufficient because we must remember where every node came from.

4. Step-by-Step Algorithm Evolution

The Naive Approach (Flawed)

Simply check if an adjacent node is marked as visited.

• The Flaw: When node 2 visits node 5, node 5 looks at its neighbors and sees node 2. Node 2 is already marked as visited! If we blindly assume any visited neighbor equals a cycle, we would falsely flag a cycle immediately between 2 and 5.

The Correct Approach: Parent Tracking

We must store both the current node and its parent in the BFS queue as a pair (node, parent).

1. Initialize a visited array of size V initialized to 0.
2. Push the source node src with a parent of -1 into the queue: Q.push({src, -1}).
3. Mark src as visited (visited[src] = 1).
4. While the queue is not empty:
   • Pop the front element (node, parent).
   • Iterate through all adjacent neighbors of node.
   • Case A (Unvisited Neighbor): Mark it visited, and push (neighbor, node) into the queue.
   • Case B (Visited Neighbor): If the neighbor is visited and neighbor != parent, a cycle is officially detected! Return true.

5. Complete Flow Walkthrough

Let us trace the algorithm on a graph where node 6 connects back to node 3 (creating a cycle).

6. Handling Disconnected Components

Real-world graphs are frequently disconnected (split into multiple islands). If we only run BFS from node 1, we might miss cycles residing in isolated components (e.g., nodes 7, 8, 9).

To guarantee complete coverage, we loop through all nodes in our graph initialization:

For i = 0 to V-1:
    If node 'i' is not visited:
        If BFS detects a cycle starting from 'i':
            Return true
Return false

7. Implementation Code (C++ & Java)

C++ Implementation

#include <bits/stdc++.h>
using namespace std;

class Solution {
private:
    bool detectCycle(int src, int V, vector<vector<int>>& adj, vector<int>& visited) {
        visited[src] = 1;
        // Queue stores {node, parent}
        queue<pair<int, int>> q;
        q.push({src, -1});

        while (!q.empty()) {
            int node = q.front().first;
            int parent = q.front().second;
            q.pop();

            for (auto neighbor : adj[node]) {
                if (!visited[neighbor]) {
                    visited[neighbor] = 1;
                    q.push({neighbor, node});
                } 
                else if (neighbor != parent) {
                    // Visited and not parent -> Cycle found!
                    return true;
                }
            }
        }
        return false;
    }

public:
    bool isCycle(int V, vector<vector<int>>& adj) {
        vector<int> visited(V, 0);
        
        // Loop handles disconnected graph components
        for (int i = 0; i < V; i++) {
            if (!visited[i]) {
                if (detectCycle(i, V, adj, visited)) return true;
            }
        }
        return false;
    }
};

Java Implementation

import java.util.*;

class Solution {
    private boolean detectCycle(int src, int V, ArrayList<ArrayList<Integer>> adj, int[] visited) {
        visited[src] = 1;
        Queue<Pair> q = new LinkedList<>();
        q.add(new Pair(src, -1));

        while (!q.isEmpty()) {
            int node = q.peek().node;
            int parent = q.peek().parent;
            q.poll();

            for (Integer neighbor : adj.get(node)) {
                if (visited[neighbor] == 0) {
                    visited[neighbor] = 1;
                    q.add(new Pair(neighbor, node));
                } 
                else if (neighbor != parent) {
                    return true;
                }
            }
        }
        return false;
    }

    public boolean isCycle(int V, ArrayList<ArrayList<Integer>> adj) {
        int[] visited = new int[V];
        Arrays.fill(visited, 0);

        for (int i = 0; i < V; i++) {
            if (visited[i] == 0) {
                if (detectCycle(i, V, adj, visited)) return true;
            }
        }
        return false;
    }
}

class Pair {
    int node;
    int parent;
    Pair(int node, int parent) {
        this.node = node;
        this.parent = parent;
    }
}

8. Complexity Analysis

9. Summary and Key Takeaways

• Definition of a Cycle: In an undirected graph, a cycle exists if we reach a previously visited node via a path other than the direct edge we just came from.
• Queue State: The BFS queue must store pairs containing both the current node and its parent node: (node, parent).
• Unvisited Check: If a neighbor is unvisited, mark it as visited, record its parent as the current node, and push it into the queue.
• Cycle Condition: If a neighbor is already visited and does not equal the parent, a cycle is confirmed.
• Disconnected Graphs: Always wrap your traversal logic in a component-checking loop (for i = 0 to V-1) to ensure isolated graph sections are not ignored.
• Time and Space Efficiency: Operates in optimal $O(N + 2E)$ time and $O(N)$ space.