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



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
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
addEdge(0, 1) 
addEdge(0, 2) 
addEdge(0, 3) 
addEdge(1, 3)
addEdge(2, 1) 
addEdge(2, 3) 
if isCyclic(): 
Scroll to Top
[gravityforms id="5" description="false" titla="false" ajax="true"]