Cycle Detection (Undirected Graph)

Cycle Detection in Undirected Graphs

Detecting cycles in an undirected graph is a common problem in graph theory. A cycle in an undirected graph is a path that starts and ends at the same vertex, and visits at least one other vertex.

Key Concepts

• DFS (Depth-First Search): The most common approach for cycle detection in undirected graphs.
• Visited Array/Set: To keep track of visited nodes during DFS.
• Parent Tracking: Crucial for undirected graphs to distinguish between a back-edge (which indicates a cycle) and an edge to the parent in the DFS tree (which is not a cycle).

Algorithm Steps (using DFS)

1. Create a visited array or set, initialized to False for all nodes.

2. For each vertex u in the graph: a. If u has not been visited: i. Call a recursive helper function dfs_util(u, parent, visited). ii. If dfs_util returns True, a cycle is found in the graph.

3. In the dfs_util(u, parent, visited) function: a. Mark u as visited. b. For each neighbor v of u: i. If v has not been visited: 1. Recursively call dfs_util(v, u, visited). 2. If the recursive call returns True, return True (cycle found). ii. Else if v is not the parent of u: 1. Return True (a cycle is found, as v is visited and not the immediate parent).

4. If the loop finishes without returning True, return False (no cycle found from this path).

Python Code Example

from collections import defaultdict

class Graph:
    def __init__(self, vertices):
        self.V = vertices
        self.graph = defaultdict(list)

    def add_edge(self, u, v):
        self.graph[u].append(v)
        self.graph[v].append(u) # For undirected graph

    def dfs_util(self, v, parent, visited):
        visited[v] = True

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

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

# Example Usage
g1 = Graph(5)
g1.add_edge(0, 1)
g1.add_edge(1, 2)
g1.add_edge(2, 0)
g1.add_edge(1, 3)
g1.add_edge(3, 4)

if g1.has_cycle():
    print("Graph contains cycle")
else:
    print("Graph does not contain cycle")

g2 = Graph(3)
g2.add_edge(0, 1)
g2.add_edge(1, 2)

if g2.has_cycle():
    print("Graph contains cycle")
else:
    print("Graph does not contain cycle")

Time and Space Complexity

• Time Complexity: O(V + E), where V is the number of vertices and E is the number of edges, as each vertex and edge is visited once.
• Space Complexity: O(V) for the visited array and recursion stack.