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.

Example Input

Expected Output

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")