 # Detect Cycle in a Directed Graph

### Problem Statement

Given the directed, connected and unweighted graph G and the task to check whether the graph contains a cycle or not.

No

### Approach

The approach is to use Depth First Traversal to detect a cycle in a Graph. While traversing through the graph if previous node visited node is encountered again this means cycle is present. If cycle is present then print “Yes” otherwise “No”.

### Implementation in Python

```from collections import defaultdict

Graph = []
V = 0
def gragh_add(x):
global Graph, V
Graph = defaultdict(list)
V = x

def addEdge(u,v):
global Graph
Graph[u].append(v)

def Solution(v, Check_Visited, Result):
Check_Visited[v] = True
Result[v] = True

for vertices in Graph[v]:
if Check_Visited[vertices] == False:
if Solution(vertices, Check_Visited, Result) == True:
return True
elif Result[vertices] == True:
return True

Result[v] = False
return False

def isCyclic():
Check_Visited = [False] * V
Result = [False] * V
for node in range(V):
if Check_Visited[node] == False:
if Solution(node,Check_Visited,Result) == True:
return True
return False

gragh_add(4)
addEdge(0, 1)
addEdge(0, 2)
addEdge(0, 3)
addEdge(1, 3)
addEdge(2, 1)
addEdge(2, 3)
if isCyclic():
print("Yes")
else:
print("No")```
Scroll to Top

### Full Stack Integrated Bootcamp Free Trial

• Please enter a number from 7000000000 to 9999999999.