Detect Cycle in a Directed Graph

Detecting a cycle in a directed graph is a common problem in graph theory, often solved using algorithms like Depth First Search (DFS). Below are explanations and approaches to solving this problem:

Algorithm to Detect a Cycle in a Directed Graph

1. Depth First Search (DFS) with Recursion

• Use two arrays:
  • Visited array: To keep track of all visited nodes.
  • Recursion stack: To track nodes in the current recursion stack.
• A cycle is detected if a node is revisited while still in the recursion stack.

Steps:

1. Traverse each node using DFS.
2. Mark the node as visited and add it to the recursion stack.
3. If an adjacent node is already in the recursion stack, a cycle is detected.
4. After visiting all adjacent nodes, remove the current node from the recursion stack.

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)

    def is_cyclic_util(self, node, visited, rec_stack):
        visited[node] = True
        rec_stack[node] = True

        for neighbor in self.graph[node]:
            if not visited[neighbor]:
                if self.is_cyclic_util(neighbor, visited, rec_stack):
                    return True
            elif rec_stack[neighbor]:
                return True

        rec_stack[node] = False
        return False

    def is_cyclic(self):
        visited = [False] * self.V
        rec_stack = [False] * self.V

        for node in range(self.V):
            if not visited[node]:
                if self.is_cyclic_util(node, visited, rec_stack):
                    return True
        return False


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

if g.is_cyclic():
    print("Graph contains a cycle")
else:
    print("Graph does not contain a cycle")

2. Kahn’s Algorithm (BFS-Based Approach)

• Kahn’s algorithm is a topological sorting algorithm that can detect a cycle in a directed graph.
• A graph with a topological sort exists if and only if there is no cycle.

Steps:

1. Calculate the in-degree of all nodes.
2. Use a queue to process nodes with an in-degree of zero.
3. Remove the processed node and decrement the in-degree of its neighbors.
4. If the processed nodes count is less than the total number of nodes, there is a cycle.

Python Implementation of Kahn’s Algorithm

from collections import defaultdict, deque

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

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

    def is_cyclic(self):
        in_degree = [0] * self.V

        # Calculate in-degrees of all vertices
        for u in self.graph:
            for v in self.graph[u]:
                in_degree[v] += 1

        # Queue for all vertices with in-degree 0
        queue = deque([i for i in range(self.V) if in_degree[i] == 0])
        count = 0

        while queue:
            node = queue.popleft()
            count += 1

            for neighbor in self.graph[node]:
                in_degree[neighbor] -= 1
                if in_degree[neighbor] == 0:
                    queue.append(neighbor)

        # If count is less than the number of vertices, there is a cycle
        return count != self.V


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

if g.is_cyclic():
    print("Graph contains a cycle")
else:
    print("Graph does not contain a cycle")

When to Use Each Approach

1. DFS-based approach:
   • Best suited for scenarios where recursion and backtracking are more intuitive.
   • Simpler to implement for small to medium-sized graphs.
2. Kahn’s Algorithm:
   • Works well with large graphs where in-degree calculations are efficient.
   • Easier to understand for those familiar with topological sorting.

Key Points

• A directed graph contains a cycle if and only if it is not a Directed Acyclic Graph (DAG).
• The choice of algorithm depends on your familiarity and the problem constraints.