**Photo by Verpex**

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!

## Leave a Reply