Detect Cycle in an Undirected Graph Using BFS - Visualization

Graphs

Contents

VisualizationProblemExamplesSolutionAlgorithmCodeTimeSpace

Visualization Player

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❯

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.

Algorithm Steps❯

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

Code

C
C++
Python
Java
JS
Go
Rust
Kotlin
Swift
TS
#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;
}

Time Complexity❯

CaseTime ComplexityExplanation
Best CaseO(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 CaseO(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 CaseO(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.


Comments

💬 Please keep your comment relevant and respectful. Avoid spamming, offensive language, or posting promotional/backlink content.
All comments are subject to moderation before being published.

Loading comments...