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.
Comments
Loading comments...