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

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define MAX 100

typedef struct {
    int node;
    int parent;
} QueueNode;

bool bfs(int graph[MAX][MAX], int vertices, int start, bool visited[]) {
    QueueNode queue[MAX];
    int front = 0, rear = 0;

    visited[start] = true;
    queue[rear++] = (QueueNode){start, -1};

    while (front < rear) {
        QueueNode current = queue[front++];

        for (int i = 0; i < vertices; i++) {
            if (graph[current.node][i]) {
                if (!visited[i]) {
                    visited[i] = true;
                    queue[rear++] = (QueueNode){i, current.node};
                } else if (i != current.parent) {
                    return true; // Cycle detected
                }
            }
        }
    }
    return false;
}

bool hasCycle(int graph[MAX][MAX], int vertices) {
    bool visited[MAX] = {false};
    for (int i = 0; i < vertices; i++) {
        if (!visited[i]) {
            if (bfs(graph, vertices, i, visited)) {
                return true;
            }
        }
    }
    return false;
}

int main() {
    int graph[MAX][MAX] = {0};
    int vertices = 3;
    graph[0][1] = graph[1][0] = 1;
    graph[1][2] = graph[2][1] = 1;
    graph[2][0] = graph[0][2] = 1;

    if (hasCycle(graph, vertices))
        printf("Cycle detected\n");
    else
        printf("No cycle detected\n");
    return 0;
}

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

bool bfs(int start, const vector<vector<int>>& graph, vector<bool>& visited) {
    queue<pair<int, int>> q;
    q.push({start, -1});
    visited[start] = true;

    while (!q.empty()) {
        auto [node, parent] = q.front(); q.pop();
        for (int neighbor : graph[node]) {
            if (!visited[neighbor]) {
                visited[neighbor] = true;
                q.push({neighbor, node});
            } else if (neighbor != parent) {
                return true;
            }
        }
    }
    return false;
}

bool hasCycle(const vector<vector<int>>& graph) {
    int n = graph.size();
    vector<bool> visited(n, false);
    for (int i = 0; i < n; ++i) {
        if (!visited[i] && bfs(i, graph, visited)) {
            return true;
        }
    }
    return false;
}

int main() {
    vector<vector<int>> graph = {{1, 2}, {0, 2}, {0, 1}};
    cout << "Cycle detected: " << boolalpha << hasCycle(graph) << endl;
    return 0;
}

from collections import deque

def has_cycle(graph):
    visited = set()

    def bfs(start):
        queue = deque([(start, -1)])
        visited.add(start)

        while queue:
            node, parent = queue.popleft()
            for neighbor in graph.get(node, []):
                if neighbor not in visited:
                    visited.add(neighbor)
                    queue.append((neighbor, node))
                elif neighbor != parent:
                    return True
        return False

    for node in graph:
        if node not in visited:
            if bfs(node):
                return True
    return False

graph = {0: [1, 2], 1: [0, 2], 2: [0, 1]}
print("Cycle detected:", has_cycle(graph))

import java.util.*;

public class CycleDetector {
    public static boolean hasCycle(Map<Integer, List<Integer>> graph) {
        Set<Integer> visited = new HashSet<>();

        for (int node : graph.keySet()) {
            if (!visited.contains(node) && bfs(node, graph, visited)) {
                return true;
            }
        }
        return false;
    }

    private static boolean bfs(int start, Map<Integer, List<Integer>> graph, Set<Integer> visited) {
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{start, -1});
        visited.add(start);

        while (!queue.isEmpty()) {
            int[] pair = queue.poll();
            int node = pair[0], parent = pair[1];

            for (int neighbor : graph.getOrDefault(node, new ArrayList<>())) {
                if (!visited.contains(neighbor)) {
                    visited.add(neighbor);
                    queue.add(new int[]{neighbor, node});
                } else if (neighbor != parent) {
                    return true;
                }
            }
        }
        return false;
    }

    public static void main(String[] args) {
        Map<Integer, List<Integer>> graph = new HashMap<>();
        graph.put(0, Arrays.asList(1, 2));
        graph.put(1, Arrays.asList(0, 2));
        graph.put(2, Arrays.asList(0, 1));
        System.out.println("Cycle detected: " + hasCycle(graph));
    }
}

function hasCycle(graph) {
  const visited = new Set();

  const bfs = (start) => {
    const queue = [[start, -1]];
    visited.add(start);

    while (queue.length > 0) {
      const [node, parent] = queue.shift();
      for (const 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;
  };

  for (const node in graph) {
    if (!visited.has(Number(node))) {
      if (bfs(Number(node))) {
        return true;
      }
    }
  }
  return false;
}

const graph = { 0: [1, 2], 1: [0, 2], 2: [0, 1] };
console.log("Cycle detected:", hasCycle(graph));

package main

import (
    "fmt"
)

type Node struct {
    vertex int
    parent int
}

func hasCycle(graph map[int][]int) bool {
    visited := make(map[int]bool)

    var bfs func(int) bool
    bfs = func(start int) bool {
        queue := []Node{{start, -1}}
        visited[start] = true

        for len(queue) > 0 {
            current := queue[0]
            queue = queue[1:]

            for _, neighbor := range graph[current.vertex] {
                if !visited[neighbor] {
                    visited[neighbor] = true
                    queue = append(queue, Node{neighbor, current.vertex})
                } else if neighbor != current.parent {
                    return true
                }
            }
        }
        return false
    }

    for node := range graph {
        if !visited[node] && bfs(node) {
            return true
        }
    }
    return false
}

func main() {
    graph := map[int][]int{
        0: {1, 2},
        1: {0, 2},
        2: {0, 1},
    }
    fmt.Println("Cycle detected:", hasCycle(graph))
}

use std::collections::{HashMap, HashSet, VecDeque};

fn has_cycle(graph: &HashMap<i32, Vec<i32>>) -> bool {
    let mut visited = HashSet::new();

    for &node in graph.keys() {
        if !visited.contains(&node) {
            if bfs(graph, node, &mut visited) {
                return true;
            }
        }
    }
    false
}

fn bfs(graph: &HashMap<i32, Vec<i32>>, start: i32, visited: &mut HashSet<i32>) -> bool {
    let mut queue = VecDeque::new();
    queue.push_back((start, -1));
    visited.insert(start);

    while let Some((node, parent)) = queue.pop_front() {
        for &neighbor in graph.get(&node).unwrap_or(&vec![]) {
            if !visited.contains(&neighbor) {
                visited.insert(neighbor);
                queue.push_back((neighbor, node));
            } else if neighbor != parent {
                return true;
            }
        }
    }
    false
}

fn main() {
    let mut graph = HashMap::new();
    graph.insert(0, vec![1, 2]);
    graph.insert(1, vec![0, 2]);
    graph.insert(2, vec![0, 1]);
    println!("Cycle detected: {}", has_cycle(&graph));
}

fun hasCycle(graph: Map<Int, List<Int>>): Boolean {
    val visited = mutableSetOf<Int>()

    fun bfs(start: Int): Boolean {
        val queue = ArrayDeque<Pair<Int, Int>>()
        queue.add(Pair(start, -1))
        visited.add(start)

        while (queue.isNotEmpty()) {
            val (node, parent) = queue.removeFirst()
            for (neighbor in graph[node] ?: emptyList()) {
                if (neighbor !in visited) {
                    visited.add(neighbor)
                    queue.add(Pair(neighbor, node))
                } else if (neighbor != parent) {
                    return true
                }
            }
        }
        return false
    }

    for (node in graph.keys) {
        if (node !in visited && bfs(node)) {
            return true
        }
    }
    return false
}

fun main() {
    val graph = mapOf(0 to listOf(1, 2), 1 to listOf(0, 2), 2 to listOf(0, 1))
    println("Cycle detected: ${hasCycle(graph)}")
}

import Foundation

func hasCycle(_ graph: [Int: [Int]]) -> Bool {
    var visited = Set<Int>()

    func bfs(_ start: Int) -> Bool {
        var queue = [(start, -1)]
        visited.insert(start)

        while !queue.isEmpty {
            let (node, parent) = queue.removeFirst()
            for neighbor in graph[node] ?? [] {
                if !visited.contains(neighbor) {
                    visited.insert(neighbor)
                    queue.append((neighbor, node))
                } else if neighbor != parent {
                    return true
                }
            }
        }
        return false
    }

    for node in graph.keys {
        if !visited.contains(node) && bfs(node) {
            return true
        }
    }
    return false
}

let graph = [0: [1, 2], 1: [0, 2], 2: [0, 1]]
print("Cycle detected: \(hasCycle(graph))")

function hasCycle(graph: Record<number, number[]>): boolean {
  const visited = new Set<number>();

  const bfs = (start: number): boolean => {
    const queue: [number, number][] = [[start, -1]];
    visited.add(start);

    while (queue.length > 0) {
      const [node, parent] = queue.shift()!;
      for (const neighbor of graph[node] || []) {
        if (!visited.has(neighbor)) {
          visited.add(neighbor);
          queue.push([neighbor, node]);
        } else if (neighbor !== parent) {
          return true;
        }
      }
    }
    return false;
  };

  for (const node in graph) {
    const n = Number(node);
    if (!visited.has(n) && bfs(n)) {
      return true;
    }
  }
  return false;
}

const graph = { 0: [1, 2], 1: [0, 2], 2: [0, 1] };
console.log("Cycle detected:", hasCycle(graph));

Time complexity

Space complexity

O(V)

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