Undirected Graph Cycle
Given an undirected graph with V vertices labelled from 0 to V-1 and E edges, check whether the graph contains any cycle or not. The Graph is represented as an adjacency list, where adj[i] contains all the vertices that are directly connected to vertex i.
NOTE: The adjacency list represents undirected edges, meaning that if there is an edge between vertex i and vertex j, both j will be adj[i] and i will be in adj[j].
Examples:
Input: adj = [[1], [0,2,4], [1,3], [2,4], [1,3]] Output: 1 Explanation: 1->2->3->4->1 is a cycle.
Input: adj = [[], [2], [1,3], [2]] Output: 0 Explanation: No cycle in the graph.
Constraints:
1 ≤ adj.size() ≤ 105
To solve the problem of detecting cycles in an undirected graph, we can utilize a Depth First Search (DFS) approach. Here's how we can approach this problem:
Approach:
-
DFS Traversal:
- We can traverse the graph using DFS. During the traversal, we'll keep track of visited vertices and the parent of each vertex (the vertex from which we arrived).
- For each vertex, we check its adjacent vertices:
- If an adjacent vertex is not visited, we recursively explore it.
- If an adjacent vertex is already visited and is not the parent of the current vertex, it means we've encountered a cycle.
-
Parent Tracking:
- The parent tracking is necessary because in an undirected graph, we would otherwise falsely detect a cycle when traversing back to the vertex from which we came.
-
Edge Case:
- If the graph is disconnected, we need to perform DFS from all unvisited vertices to ensure every component is checked.
Code Implementation (C#):
using System;
using System.Collections.Generic;
public class Solution {
// Helper function to perform DFS and detect cycle
private bool DFS(int v, int parent, List<List<int>> adj, bool[] visited) {
visited[v] = true;
foreach (int neighbor in adj[v]) {
// If neighbor is not visited, explore it recursively
if (!visited[neighbor]) {
if (DFS(neighbor, v, adj, visited)) {
return true; // cycle detected
}
}
// If neighbor is visited and is not the parent, cycle is detected
else if (neighbor != parent) {
return true;
}
}
return false;
}
public int ContainsCycle(List<List<int>> adj) {
int V = adj.Count;
bool[] visited = new bool[V];
// Perform DFS for every unvisited vertex
for (int i = 0; i < V; i++) {
if (!visited[i]) {
if (DFS(i, -1, adj, visited)) {
return 1; // cycle found
}
}
}
return 0; // no cycle found
}
}
class Program {
static void Main(string[] args) {
Solution solution = new Solution();
// Example 1: Graph with a cycle
var adj1 = new List<List<int>> {
new List<int> { 1 },
new List<int> { 0, 2, 4 },
new List<int> { 1, 3 },
new List<int> { 2, 4 },
new List<int> { 1, 3 }
};
Console.WriteLine(solution.ContainsCycle(adj1)); // Output: 1 (Cycle exists)
// Example 2: Graph without a cycle
var adj2 = new List<List<int>> {
new List<int> { },
new List<int> { 2 },
new List<int> { 1, 3 },
new List<int> { 2 }
};
Console.WriteLine(solution.ContainsCycle(adj2)); // Output: 0 (No cycle)
}
}
Explanation of the Code:
-
DFS Function:
-
The
DFS
function explores the graph recursively:- The
v
parameter represents the current vertex. - The
parent
parameter is the vertex from which we came to the current vertex. - The
adj
parameter is the adjacency list representing the graph. - The
visited
array keeps track of which vertices have been visited.
- The
-
We mark the current vertex
v
as visited. -
For each neighboring vertex, we check:
- If the neighbor is not visited, we recursively perform DFS on that neighbor.
- If the neighbor is visited and it's not the parent, it means we've encountered a cycle.
-
-
ContainsCycle Function:
- The
ContainsCycle
function initializes the visited array and performs DFS for each unvisited vertex. If a cycle is found during any DFS call, it returns 1, otherwise 0.
- The
-
Graph Input:
- The graph is represented as an adjacency list, which is a list of lists where each index represents a vertex and contains a list of vertices that are adjacent to it.
Time and Space Complexity:
-
Time Complexity: , where is the number of vertices and is the number of edges. In the worst case, we visit each vertex and each edge once.
-
Space Complexity: , where is the number of vertices. We use an array to track visited vertices and recursion stack for DFS.
Edge Cases:
- Graph with no edges (empty graph):
- If the graph has no edges, it doesn't contain a cycle. The output will be
0
.
- If the graph has no edges, it doesn't contain a cycle. The output will be
- Disconnected graph:
- If the graph is disconnected, we perform DFS starting from every unvisited vertex to ensure we check all components.
Examples:
-
Input:
adj = [[1], [0,2,4], [1,3], [2,4], [1,3]]
- Output: 1 (There is a cycle: 1 → 2 → 3 → 4 → 1)
-
Input:
adj = [[], [2], [1,3], [2]]
- Output: 0 (No cycle, it's a tree)
This approach efficiently checks for cycles in an undirected graph using DFS with a time complexity of .
credits: GeeksforGeeks