Detect cycle in an undirected graph using DFS

Learn how to detect a cycle in an undirected graph with a depth-first search (DFS) approach. This beginner-friendly guide walks you through the code, adds helpful comments, and explains each step in plain English.

What the Problem Asks?

GFG “Detect Cycle in an Undirected Graph”
You’re given an undirected graph with V vertices (numbered 0 to V-1) and a list of edges. Determine whether the graph contains at least one cycle.

• Input:
  • V: number of vertices
  • edges: list of pairs [u, v], each an undirected edge between u and v
• Output:
  • True if there is a cycle, False otherwise

Intuition & Approach

1. Depth-First Search (DFS):
   • We start DFS from each unvisited node.
   • We mark nodes as visited and, for each node, explore its neighbors recursively.
2. Detecting a Cycle:
   • In an undirected graph, every edge appears in both adjacency lists (u→v and v→u).
   • When we move from node to adjNode, we pass node as the “parent.”
   • If during DFS we reach a neighbor that is already visited but is not the parent, it means there’s another back-edge → a cycle.
3. Handling Disconnected Graphs:
   • We loop over all vertices and start a DFS from any vertex that hasn’t been visited yet.

Code Implementation

class Solution:
    def dfs(self, node, parent, visited, adj_list):
        # Mark the current node as visited
        visited[node] = 1
        
        # Explore all neighbors
        for adjNode in adj_list[node]:
            # If neighbor not visited, recurse
            if visited[adjNode] == 0:
                if self.dfs(adjNode, node, visited, adj_list):
                    return True
            # If neighbor visited and not the parent, cycle found
            elif adjNode != parent:
                return True
        
        # No cycle found along this path
        return False

    def isCycle(self, V, edges):
        # Build adjacency list
        adj_list = [[] for _ in range(V)]
        for u, v in edges:
            adj_list[u].append(v)
            adj_list[v].append(u)
        
        visited = [0] * V  # 0 = unvisited, 1 = visited
        
        # Try DFS from each unvisited vertex
        for i in range(V):
            if visited[i] == 0:
                # If DFS finds a cycle, return True immediately
                if self.dfs(i, -1, visited, adj_list):
                    return True
        
        # No cycle found in any component
        return False

Step-by-Step Explanation

1. Build the adjacency list so we can quickly look up neighbors of any vertex.
2. visited array keeps track of which vertices we’ve already explored.
3. We loop through every vertex i. If it’s unvisited, we call dfs(i, parent=-1, ...).
4. Inside dfs(node, parent):
   • Mark node visited.
   • For each neighbor adjNode of node:
     • If unvisited, recurse dfs(adjNode, node). If that recursion finds a cycle, bubble True up.
     • If visited and adjNode != parent, we found a back-edge that isn’t just going back to our parent → a cycle.
5. If any DFS call returns True, isCycle returns True. If we finish all vertices without finding a cycle, return False.

Dry Run Example

V = 4
edges = [[0,1],[1,2],[2,0],[2,3]]

• Adjacency list: makefileCopy0: [1,2] 1: [0,2] 2: [1,0,3] 3: [2]
• Start DFS at 0 (parent = -1):
  • Visit 0 → explore neighbor 1
    • Visit 1 (parent=0) → neighbor 0 is parent (ignore), neighbor 2
      • Visit 2 (parent=1) → neighbor 1 is parent, neighbor 0 is visited and not parent → cycle detected → return True.

Time & Space Complexity

• Time Complexity: O(V + 2E)
  • We visit each vertex once and explore each edge once in the worst case.
• Space Complexity: O(V + 2E)
  • Adjacency list uses O(V+E), and recursion stack can use up to O(V) in a worst-case chain.

Conclusion

By doing a simple DFS from every unvisited node and checking for visited neighbors that aren’t the parent, we can detect cycles in an undirected graph in linear time. This pattern of passing the parent into DFS is key to handling undirected edges correctly. Happy graph traversing!

For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.