DSA Graphs Cycle Detection

Welcome to TheCodingCollege.com! In this guide, we’ll explore cycle detection in graphs, one of the most critical topics in Data Structures and Algorithms (DSA). Understanding how to detect cycles in directed and undirected graphs is essential for solving problems like deadlock detection, scheduling, and dependency management.

What is a Cycle in a Graph?

A cycle in a graph occurs when a path starts and ends at the same vertex, with all edges and vertices in the path being distinct (except the starting and ending vertex).

• In undirected graphs, a cycle forms when at least three vertices connect in a closed loop.
• In directed graphs, a cycle occurs when there is a path from a vertex back to itself following the direction of edges.

Cycle Detection in Undirected Graphs

Approach: Using Depth-First Search (DFS)

In an undirected graph, a cycle exists if, during a DFS traversal, we visit an already visited vertex that is not the parent of the current vertex.

Algorithm

1. Perform a DFS traversal.
2. For each vertex:
   • Mark it as visited.
   • Check its neighbors.
   • If a neighbor is visited and not the parent of the current vertex, a cycle exists.

Implementation in Python

def is_cycle_undirected(graph, visited, vertex, parent):
    visited[vertex] = True
    for neighbor in graph[vertex]:
        if not visited[neighbor]:
            if is_cycle_undirected(graph, visited, neighbor, vertex):
                return True
        elif neighbor != parent:
            return True
    return False

def detect_cycle_undirected(graph, vertices):
    visited = [False] * vertices
    for v in range(vertices):
        if not visited[v]:
            if is_cycle_undirected(graph, visited, v, -1):
                return True
    return False

# Example Usage
graph = {
    0: [1, 2],
    1: [0, 2],
    2: [0, 1, 3],
    3: [2]
}
vertices = 4
print("Cycle Detected in Undirected Graph:" if detect_cycle_undirected(graph, vertices) else "No Cycle Detected")

Cycle Detection in Directed Graphs

Approach: Using Depth-First Search (DFS)

In a directed graph, a cycle exists if we encounter a vertex that is already in the recursion stack during DFS traversal.

Algorithm

1. Maintain a visited array and a rec_stack (recursion stack).
2. For each vertex:
   • Mark it as visited.
   • Add it to the recursion stack.
   • Check all neighbors:
     • If a neighbor is in the recursion stack, a cycle exists.
     • Otherwise, continue DFS.
   • Remove the vertex from the recursion stack after processing.

Implementation in Python

def is_cycle_directed(graph, visited, rec_stack, vertex):
    visited[vertex] = True
    rec_stack[vertex] = True
    for neighbor in graph[vertex]:
        if not visited[neighbor]:
            if is_cycle_directed(graph, visited, rec_stack, neighbor):
                return True
        elif rec_stack[neighbor]:
            return True
    rec_stack[vertex] = False
    return False

def detect_cycle_directed(graph, vertices):
    visited = [False] * vertices
    rec_stack = [False] * vertices
    for v in range(vertices):
        if not visited[v]:
            if is_cycle_directed(graph, visited, rec_stack, v):
                return True
    return False

# Example Usage
graph = {
    0: [1],
    1: [2],
    2: [3],
    3: [1]  # Cycle: 1 -> 2 -> 3 -> 1
}
vertices = 4
print("Cycle Detected in Directed Graph:" if detect_cycle_directed(graph, vertices) else "No Cycle Detected")

Using Disjoint Set (Union-Find) for Undirected Graphs

For undirected graphs, the disjoint set (Union-Find) algorithm can detect cycles efficiently.

Algorithm

1. Initialize a parent array for all vertices.
2. For each edge:
   • Find the root of both vertices.
   • If the roots are the same, a cycle exists.
   • Otherwise, union the two vertices.

Implementation in Python

class DisjointSet:
    def __init__(self, vertices):
        self.parent = list(range(vertices))
    
    def find(self, vertex):
        if self.parent[vertex] == vertex:
            return vertex
        self.parent[vertex] = self.find(self.parent[vertex])  # Path compression
        return self.parent[vertex]
    
    def union(self, v1, v2):
        root1 = self.find(v1)
        root2 = self.find(v2)
        if root1 != root2:
            self.parent[root2] = root1

def detect_cycle_union_find(edges, vertices):
    ds = DisjointSet(vertices)
    for v1, v2 in edges:
        if ds.find(v1) == ds.find(v2):
            return True
        ds.union(v1, v2)
    return False

# Example Usage
edges = [(0, 1), (1, 2), (2, 0)]  # Cycle: 0 -> 1 -> 2 -> 0
vertices = 3
print("Cycle Detected using Union-Find:" if detect_cycle_union_find(edges, vertices) else "No Cycle Detected")

Applications of Cycle Detection

1. Deadlock Detection:
   • Detecting cycles in a resource allocation graph can prevent deadlocks.
2. Dependency Management:
   • Ensuring no circular dependencies exist in task or package graphs.
3. Topology Validation:
   • Validating if a directed graph is a Directed Acyclic Graph (DAG).

Comparison of Approaches

Conclusion

Detecting cycles in graphs is an essential problem-solving technique in DSA. Whether you’re working with directed or undirected graphs, understanding different approaches like DFS and Union-Find equips you to handle real-world challenges.