Detect Cycle in UnDirected Graph using BFS DFS Algo
Problem Statement
Given an undirected graph with V vertices and E edges, detect whether the graph contains a cycle.
Example:
- Input:
V = 5, Edges = [[0,1],[1,2],[2,3],[3,4],[4,1]] - Output:
true(cycle: 1 → 2 → 3 → 4 → 1)
Noob-Friendly Explanation
Imagine you're walking through a network of hallways. You mark every hallway intersection you visit. If you ever reach an intersection you've already marked — and it's NOT the one you just came from — you've walked in a circle! That's a cycle.
In an undirected graph, edges go both ways. So if A connects to B, then B also connects to A. We need to be careful: going from A to B and back to A is NOT a cycle (that's just retracing your steps). A real cycle involves at least 3 different nodes.
Approach 1: Brute Force (BFS)
Intuition
Use BFS traversal. For each vertex, track which vertex we came from (the parent). If we find a neighbor that is already visited and it's NOT our parent, we found a cycle.
Algorithm
- Build an adjacency list.
- For each unvisited vertex, start BFS.
- Use a queue that stores pairs of (node, parent).
- If a neighbor is visited and not the parent, return true (cycle found).
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
public class CycleUndirectedBFS {
static boolean bfsCycleCheck(List<List<Integer>> adj, boolean[] visited, int start) {
Queue<int[]> queue = new LinkedList<>(); // {node, parent}
visited[start] = true;
queue.add(new int[]{start, -1});
while (!queue.isEmpty()) {
int[] curr = queue.poll();
int node = curr[0];
int parent = curr[1];
for (int neighbor : adj.get(node)) {
if (!visited[neighbor]) {
visited[neighbor] = true;
queue.add(new int[]{neighbor, node});
} else if (neighbor != parent) {
return true; // cycle detected
}
}
}
return false;
}
public static boolean hasCycle(int V, int[][] edges) {
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i < V; i++) {
adj.add(new ArrayList<>());
}
for (int[] edge : edges) {
adj.get(edge[0]).add(edge[1]);
adj.get(edge[1]).add(edge[0]);
}
boolean[] visited = new boolean[V];
for (int i = 0; i < V; i++) {
if (!visited[i]) {
if (bfsCycleCheck(adj, visited, i)) {
return true;
}
}
}
return false;
}
public static void main(String[] args) {
int V = 5;
int[][] edges = {{0,1},{1,2},{2,3},{3,4},{4,1}};
System.out.println(hasCycle(V, edges)); // true
}
}Complexity Analysis
- Time Complexity: O(V + E) — each vertex and edge is processed once.
- Space Complexity: O(V) — for the visited array and queue.
Approach 2: Optimal (DFS)
Intuition
Use DFS and track the parent of each vertex. If during DFS we encounter a visited neighbor that isn't our parent, there's a cycle.
Algorithm
- Build an adjacency list.
- For each unvisited vertex, start DFS with parent = -1.
- Mark vertex as visited. For each neighbor:
- If not visited, recurse with current vertex as parent.
- If visited and not parent, cycle found.
import java.util.ArrayList;
import java.util.List;
public class CycleUndirectedDFS {
static boolean dfs(List<List<Integer>> adj, boolean[] visited, int node, int parent) {
visited[node] = true;
for (int neighbor : adj.get(node)) {
if (!visited[neighbor]) {
if (dfs(adj, visited, neighbor, node)) {
return true;
}
} else if (neighbor != parent) {
return true; // cycle detected
}
}
return false;
}
public static boolean hasCycle(int V, int[][] edges) {
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i < V; i++) {
adj.add(new ArrayList<>());
}
for (int[] edge : edges) {
adj.get(edge[0]).add(edge[1]);
adj.get(edge[1]).add(edge[0]);
}
boolean[] visited = new boolean[V];
for (int i = 0; i < V; i++) {
if (!visited[i]) {
if (dfs(adj, visited, i, -1)) {
return true;
}
}
}
return false;
}
public static void main(String[] args) {
int V = 5;
int[][] edges = {{0,1},{1,2},{2,3},{3,4},{4,1}};
System.out.println(hasCycle(V, edges)); // true
}
}Complexity Analysis
- Time Complexity: O(V + E) — each vertex and edge is visited once.
- Space Complexity: O(V) — for the visited array and recursion stack.