Detect a cycle in an undirected graph

1. Graph Representation: Use an adjacency list to represent the graph.
2. DFS Traversal: Perform a DFS traversal of the graph.
3. Cycle Detection:
   • During DFS, track the parent node to avoid revisiting the immediate parent.
   • If you encounter a visited node that is not the parent of the current node, a cycle is detected.

Python Implementation

from collections import defaultdict

class Graph:
    def __init__(self, vertices):
        self.graph = defaultdict(list)
        self.V = vertices
    
    def add_edge(self, u, v):
        self.graph[u].append(v)
        self.graph[v].append(u)  # Since it's an undirected graph
    
    def is_cycle_util(self, v, visited, parent):
        visited[v] = True

        for neighbor in self.graph[v]:
            if not visited[neighbor]:
                if self.is_cycle_util(neighbor, visited, v):
                    return True
            elif parent != neighbor:
                return True

        return False

    def is_cycle(self):
        visited = [False] * self.V
        
        for i in range(self.V):
            if not visited[i]:
                if self.is_cycle_util(i, visited, -1):
                    return True
        
        return False

# Example usage:
g = Graph(5)
g.add_edge(0, 1)
g.add_edge(1, 2)
g.add_edge(2, 0)
g.add_edge(1, 3)
g.add_edge(3, 4)

if g.is_cycle():
    print("Graph contains cycle")
else:
    print("Graph doesn't contain cycle")

Explanation:

• is_cycle_util Function: This recursive function performs the DFS and checks for cycles.

  • visited[v] = True marks the current node as visited.
  • The loop iterates through all neighbors of the current node.
  • If a neighbor hasn't been visited, the function recurses.
  • If a neighbor has been visited and isn't the parent of the current node, a cycle is detected.

• is_cycle Function: Iterates over all vertices to ensure all connected components are checked for cycles.

Example Output:

Given the example graph, the output will be:

Graph contains cycle

This approach ensures that all nodes and edges are checked, making it a reliable way to detect cycles in an undirected graph.