Create a Program to Detect Cycles in a Graph Using DFS in Python

You can implement a program to detect cycles in a graph using Depth-First Search (DFS) in Python. Here is a step-by-step solution:

Code for Cycle Detection in a Directed Graph Using DFS:

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 _dfs_cycle_util(self, v, visited, rec_stack):
        # Mark the current node as visited and add it to recursion stack
        visited[v] = True
        rec_stack[v] = True

        # Recur for all neighbours
        for neighbour in self.graph[v]:
            # If the neighbour is not visited, recurse for it
            if not visited[neighbour]:
                if self._dfs_cycle_util(neighbour, visited, rec_stack):
                    return True
            # If the neighbour is already in the recursion stack, there's a cycle
            elif rec_stack[neighbour]:
                return True

        # Remove the vertex from the recursion stack
        rec_stack[v] = False
        return False

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

        # Call the recursive helper function to detect cycle in different DFS trees
        for node in range(self.V):
            if not visited[node]:
                if self._dfs_cycle_util(node, visited, rec_stack):
                    return True
        return False


# Example usage
if __name__ == "__main__":
    g = Graph(4)
    g.add_edge(0, 1)
    g.add_edge(1, 2)
    g.add_edge(2, 0)
    g.add_edge(2, 3)

    if g.detect_cycle():
        print("Graph has a cycle")
    else:
        print("Graph has no cycle")

Explanation:

• Graph Representation: The graph is represented using an adjacency list, implemented with the defaultdict from Python’s collections module.
• DFS Utility Function (_dfs_cycle_util):
  • The function is a helper that performs DFS starting from a vertex v.
  • It keeps track of visited vertices (visited[]) and vertices in the recursion stack (rec_stack[]).
  • If a vertex is revisited in the current recursion stack, it indicates a cycle.
• Cycle Detection (detect_cycle): The main function iterates over all vertices, calling the DFS helper to detect any cycle in the graph.

Output for the example:

This graph has a cycle from vertex 0 → 1 → 2 → 0, so the output will be:

Graph has a cycle

You can modify the graph by adding/removing edges to test other scenarios. Let me know if you’d like any further clarifications!