Detect Cycle in an Undirected Graph Using BFS

Problem Statement❯

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.

Examples❯

Graph	Cycle?	Explanation
{ 0: [1, 2], 1: [0, 2], 2: [0, 1] }	Yes	0 → 1 → 2 → 0 forms a cycle
{ 0: [1], 1: [0, 2], 2: [1, 3], 3: [2] }	No	No cycle exists; it's a linear graph
{}	No	Empty graph has no cycles
{ 0: [], 1: [], 2: [] }	No	Disconnected graph with no edges
{ 0: [1], 1: [0, 2], 2: [1, 3], 3: [2, 0] }	Yes	Cycle: 0 → 1 → 2 → 3 → 0

Solution❯

Case 1: Graph with No Cycles

In a graph that forms a tree structure (i.e., no cycles and only one path between any two nodes), the BFS traversal will explore all neighbors and never encounter a node that was previously visited except its parent. This means the condition if neighbor is visited and neighbor ≠ parent never triggers, and the algorithm correctly returns false indicating no cycle.

Case 2: Graph with a Cycle

When there is a cycle, at least one node will have a neighbor that has already been visited but is not the node’s parent. This condition is a clear indicator of a back-edge, confirming the presence of a cycle. As soon as this condition is met during BFS, the algorithm immediately returns true.

Case 3: Disconnected Graph

For graphs that are not connected (i.e., consist of multiple components), the algorithm loops over every node and initiates a BFS only if the node hasn’t been visited yet. This ensures that each disconnected component is explored. If any of these components contain a cycle, it will be detected. If none do, the function returns false.

Case 4: Empty Graph

If the graph has no nodes, the loop never starts, and the function immediately returns false. This is logically sound, as an empty graph cannot contain a cycle.

Algorithm Steps❯

Initialize a visited set.
Loop over each node in the graph:

If the node is not visited, initiate BFS from that node.
Use a queue to store [current, parent] pairs.
While the queue is not empty:

Dequeue a pair [node, parent].
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.

If no such condition occurs, return false (no cycle).

Code

JavaScript

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 graph1 = { 0: [1, 2], 1: [0, 2], 2: [0, 1] };
console.log("Cycle detected:", hasCycle(graph1)); // true

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

Time Complexity❯

Case	Time Complexity	Explanation
Best Case	O(V + E)	In the best case (no cycle and early exit), every vertex and edge in the connected components must still be traversed to ensure the absence of a cycle.
Average Case	O(V + E)	Each node and edge is visited once. The BFS explores all nodes and edges reachable from each unvisited node, ensuring complete coverage.
Worst Case	O(V + E)	In the worst case, such as a complete graph, the algorithm still performs BFS for all nodes and edges before finding or ruling out a cycle.

Space Complexity❯

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.

⬅ Previous TopicDetect Cycle in an Undirected Graph using DFS

Next Topic ⮕Distance of Nearest Cell Having 1 - Grid BFS