Detect Cycle in an Undirected Graph
Problem link: https://www.geeksforgeeks.org/problems/detect-cycle-in-an-undirected-graph/1
Problem Statement
Given an undirected graph with V vertices and E edges, check whether it contains any cycle or not. The graph is represented using an adjacency list.
Input
An adjacency list adj and the number of vertices V.
Output
Boolean (true if cycle exists, false otherwise).
Example
Input: V = 5, E = 5, adj = [[1], [0, 2, 4], [1, 3], [2, 4], [1, 3]] Output: true Explanation: Node 1, 2, 3, 4 form a cycle.
Explanation
In this graph, starting from node 1, we can travel through 2, 3, and 4 and return to 1. This circular path indicates a cycle.
Brute Force
Intuition
For every node, try to see if there is a path back to itself without immediately reversing the last edge taken.
Approach
Check all possible paths using a simple recursion. However, since this is a graph, we must use a visited array to avoid infinite loops. The standard way to implement this is either BFS or DFS.
Dry Run
V=3, E=3 (0-1, 1-2, 2-0)
- Visit 0, mark visited.
- Move to 1, mark visited, parent is 0.
- Move to 2, mark visited, parent is 1.
- Check neighbors of 2: 1 (parent, skip), 0 (visited and not parent! Cycle found).
Code (Java)
class Solution {
// Standard DFS/BFS implementation is already optimal.
}
Complexity Analysis
We visit every vertex and edge once.
Optimal Solution
Intuition
We use DFS or BFS and keep track of the parent node (the node we just came from). If we reach a node that has already been visited and is NOT the parent of our current node, it means there's another path to that node, hence a cycle.
Approach
- Initialize a
visitedarray of sizeVwithfalse. - Since the graph might have multiple components, loop through all vertices
ifrom 0 toV-1. - If node
iis not visited, call theisCycleDFS(i, -1)function. - In
isCycleDFS(node, parent):- Mark
nodeas visited. - For every neighbor
adjNodeofnode:- If
adjNodeis not visited, recursively callisCycleDFS(adjNode, node). If it returns true, return true. - Else if
adjNodeis visited ANDadjNode != parent, return true (cycle found).
- If
- Mark
- If no cycle is found in any component, return false.
Dry Run
adj = [[1, 2], [0, 2], [0, 1]]
- DFS(0, -1): visited={0}
- Neighbor 1: DFS(1, 0), visited={0, 1}
- Neighbor 0 of node 1: 0 is parent, skip.
- Neighbor 2 of node 1: DFS(2, 1), visited={0, 1, 2}
- Neighbor 0 of node 2: 0 is visited and 0 != parent(1). Cycle detected!
Code (Java)
Complexity Analysis
Time: We traverse each node once and check each edge (twice for undirected graphs). Space: Visited array and recursion stack both take O(V).
Quick Revision (Brute Force)
- Traverse graph components
- O(V+E) time
Quick Revision (Optimal)
- DFS or BFS with Parent tracking
- Condition: (visited[neighbor] == true && neighbor != parent)
- Handles disconnected components with a loop
- O(V+E) time, O(V) space