Geeksforgeeks: Undirected Graph Cycle

 Undirected Graph Cycle

Difficulty: Medium

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:

  1. 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.
  2. 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.
  3. 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:

  1. 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.
    • 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.
  2. 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.
  3. 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: O(V+E)O(V + E), where VV is the number of vertices and EE is the number of edges. In the worst case, we visit each vertex and each edge once.

  • Space Complexity: O(V)O(V), where VV is the number of vertices. We use an array to track visited vertices and recursion stack for DFS.

Edge Cases:

  1. Graph with no edges (empty graph):
    • If the graph has no edges, it doesn't contain a cycle. The output will be 0.
  2. Disconnected graph:
    • If the graph is disconnected, we perform DFS starting from every unvisited vertex to ensure we check all components.

Examples:

  1. Input: adj = [[1], [0,2,4], [1,3], [2,4], [1,3]]

    • Output: 1 (There is a cycle: 1 → 2 → 3 → 4 → 1)
  2. 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 O(V+E)O(V + E).


credits: GeeksforGeeks

Featured Posts

Leetcode 4. Median of Two Sorted Arrays

  4. Median of Two Sorted Arrays Hard Given two sorted arrays  nums1  and  nums2  of size  m  and  n  respectively, return  the median  of t...

Popular Posts