# Detect Cycle in a Directed Graph

Here given code implementation process.

``````//C Program
//Detect Cycle in a Directed Graph
#include<stdio.h>
#include<stdlib.h>

struct AjlistNode
{
int vId;//Vertices id
struct AjlistNode*next;
};

struct Graph
{
int data; //node key value
struct AjlistNode*next;
};

int size; //number of nodes

//set node key value
void setData(struct Graph*node)
{
if(node!=NULL && size>0)
{
int index=0;
for(index;index<size;index++)
{
//set vertic node data
node[index].data=index;//set node key
//Initial no AjlistNode
//set NULL Value
node[index].next=NULL;
}
}else
{
printf("Vertic Node is Empty");
}
}
//Add Edge from Two given Nodes
void addEdge(struct Graph*node, int V ,int E)
{
//add edge form V to E
//V and E is Node location
if(V<size && E <size)
{
struct AjlistNode *newEdge=(struct AjlistNode*)malloc(
sizeof(struct AjlistNode)
);
if(newEdge!=NULL)
{

newEdge->next=NULL;
newEdge->vId=E;

struct AjlistNode *temp=node[V].next;

if(temp==NULL)
{
node[V].next=newEdge;
}else
{
while(temp->next!=NULL)
{
temp=temp->next;
}
temp->next=newEdge;
}
}else
{
printf("\n Memory overflow");
}
}else
{
//not valid Vertices
printf("Invalid Node Vertices %d  %d", V,E);
}
}
void printGraph(struct Graph*node)
{
if(node!=NULL)
{
struct AjlistNode *temp=NULL;
for(int index=0;index<size;index++)
{
printf("\n Adjacency list of vertex %d  :",index);
temp=node[index].next;
while(temp!=NULL)
{
//temp->vId is graph node vertices
//in this case temp->vId is same as
//node[temp->vId].data

printf("  %d",node[temp->vId].data);
temp=temp->next;
}
}
}else
{
printf("Empty Graph");
}
}

void detect_cycle(int point,int *visit,struct Graph*node,int *status)
{

if(*status!=-1)
{
if(visit[*status]==1 && point == *status)
{
*status=-1;
}else if(visit[point]==1)
{
return;
}
visit[point]=1;
struct AjlistNode *temp=node[point].next;
while(temp!=NULL)
{
if(*status!=-1)
{
detect_cycle(temp->vId,visit,node,status);
}else
{
break;
}

temp=temp->next;
}
}
}
void check_cycle(struct Graph*node)
{

if(node==NULL)
{
printf("Empty Graph\n");
return;
}
printGraph(node);
int *visit=(int*)calloc(size,sizeof(int));
int test=0,status=0;
while(test<size)
{
status=test;
detect_cycle(test,visit,node,&status);
if(status==-1)
{
break;
}
for(int index=0;index<size;index++)
{
visit[index]=0;
}
test++;
}
if(status==-1)
{

printf("\n Detect Cycle\n");
}else
{
printf("\n No Cycle\n");
}
}
int main()
{

size=6;
struct Graph*node=node=(struct Graph*)malloc(
sizeof(struct Graph)*size
);

if(node==NULL)
{
printf("\n Memory overflow");
}else
{
//First set node keys
setData(node);
//Connected two node with Edges

check_cycle(node);

//Case two
check_cycle(node);
}
return 0;
}``````

#### Output

`````` Adjacency list of vertex 0  :  1  3
Adjacency list of vertex 1  :  2
Adjacency list of vertex 2  :  5
Adjacency list of vertex 3  :  4
Adjacency list of vertex 4  :  2
Adjacency list of vertex 5  :
No Cycle

Adjacency list of vertex 0  :  1  3
Adjacency list of vertex 1  :  2
Adjacency list of vertex 2  :  5
Adjacency list of vertex 3  :  4
Adjacency list of vertex 4  :  2
Adjacency list of vertex 5  :  1
Detect Cycle
``````
``````//C++ program
//Detect Cycle in a Directed Graph
#include<iostream>
using namespace std;

struct AjlistNode
{
int vId;//Vertices id
struct AjlistNode*next;
};

struct Vertices
{
int data; //node key value
struct AjlistNode*next;
};

class Graph
{
Vertices *node;
int size;//number of
public:
Graph(int);
void setData();
void printGraph();
void check_cycle();
void detect_cycle(int ,int [],int *);
};
Graph::Graph(int size)
{
this->size = size;
//set number of nodes
node = new Vertices[size];
}
//set node key value
void Graph:: setData()
{
if(node!=NULL)
{
int index=0;

for(index;index<size;index++)
{
//set vertic node data
node[index].data=index;//set node key
//Initial no AjlistNode
//set NULL Value
node[index].next=NULL;
}
}
else
{
cout<<"Vertic Node is Empty"<<endl;
}
}
//Add Edge from Two given Nodes
void Graph ::addEdge(int V ,int E)
{
//add edge form V to E
//V and E is Node location
if(V<size && E <size)
{
AjlistNode *newEdge=new AjlistNode;

if(newEdge!=NULL)
{

newEdge->next=NULL;
newEdge->vId=E;

AjlistNode *temp=node[V].next;

if(temp==NULL)
{
node[V].next=newEdge;
}else{
while(temp->next!=NULL)
{
temp=temp->next;
}
temp->next=newEdge;
}
}
}else{
//not valid Vertices
cout<<"Invalid Node Vertices "<< V<<" "<<E;
}
}
void Graph::printGraph()
{
if(node!=NULL)
{
AjlistNode *temp=NULL;
for(int index=0; index < size; index++)
{
cout<<"\n Adjacency list of vertex "<<index<<" :";
temp=node[index].next;
while(temp!=NULL)
{
//temp->vId is graph node vertices
//in this case temp->vId is same as
//node[temp->vId].data

cout<<" "<<node[temp->vId].data;
temp=temp->next;
}
}
}else
{
cout<<"Empty Graph"<<endl;
}
}
//Detect cycle using DFS
void Graph:: detect_cycle(int point,int visit[],int *status)
{

if(*status!=-1)
{
if(visit[*status]==1 && point == *status)
{
//when visits a node are more than one
//contain cycle
*status=-1;
}
else if(visit[point]==1)
{
//when start and end node are not same then
//allow to visit same node more than once
return;
}
//Set visited status 1
visit[point]=1;

//Get the address of first edge of  current node
struct AjlistNode *temp=node[point].next;

while(temp!=NULL)
{
if(*status!=-1)
{
detect_cycle(temp->vId,visit,status);

}else
{
break;
}
//visit next edge
temp=temp->next;
}
}
}
//method which are manage finding and detecting cycle operation
void Graph:: check_cycle()
{

if(node==NULL)
{
cout<<"Empty Graph\n";
return;
}

printGraph();

//This are storing the information about visiting node status
int *visit=new int[size];

int test=0,status=0;

while(test < size)
{
//Set all visit node as zero
for(int index=0;index<size;index++)
{
visit[index]=0;
}

status=test;

detect_cycle(test,visit,&status);

if(status==-1)
{
break;
}

test++;
}
if(status==-1)
{
cout<<"\n Detect Cycle\n";
}else
{
cout<<"\n No Cycle\n";
}
}

int main()
{
//Create Object
Graph g(6);
//First set node keys
g.setData();

g.check_cycle();

//Case two
g.check_cycle();

return 0;
}``````

#### Output

`````` Adjacency list of vertex 0 : 1 3
Adjacency list of vertex 1 : 2
Adjacency list of vertex 2 : 5
Adjacency list of vertex 3 : 4
Adjacency list of vertex 4 : 2
Adjacency list of vertex 5 :
No Cycle

Adjacency list of vertex 0 : 1 3
Adjacency list of vertex 1 : 2
Adjacency list of vertex 2 : 5
Adjacency list of vertex 3 : 4
Adjacency list of vertex 4 : 2
Adjacency list of vertex 5 : 1
Detect Cycle
``````
``````//Java program
//Detect Cycle in a Directed Graph
public class MyGraph
{

static class AjlistNode
{
int id;//Vertices node key
AjlistNode next;
}
static class Vertices
{
int data;
AjlistNode next;
}

//number of Vertices
static int size;
Vertices node[];
int status;
MyGraph(int size)
{
//set value
this.size = size;
node = new Vertices[size];
status=0;
}

//set initial node value
public void setData()
{
if(node == null)
{
System.out.println("\nEmpty Graph");
}else
{
for(int index = 0; index < size; index++)
{
// avoid java.lang.nullPointerException
node[index]=new Vertices();
node[index].next=null;
}
}
}
{
if(S < size && E < size && node != null)
{
AjlistNode newEdge=new AjlistNode();
newEdge.id=E;//end node
newEdge.next=null;
if(node[S].next==null)
{
node[S].next=newEdge;
}else
{
AjlistNode temp=node[S].next;

while(temp.next!=null)
{
temp=temp.next;
}
temp.next=newEdge;
}

}else{
System.out.println("\nEmpty Graph");
}
}

public void printGraph()
{

if(size>0 && node!=null)
{
for(int index=0;index<size;index++)
{
System.out.print("\nAdjacency list of vertex "+index+" :");

AjlistNode temp=node[index].next;

while(temp!=null)
{
System.out.print(" "+node[temp.id].data);

temp=temp.next;
}
}
}
}
//Detect cycle using DFS
public void detectCycle(int point,int visit[])
{

if( status != -1)
{
if(visit[status] == 1 && point ==  status)
{
//when visits a node are more than one
//contain cycle
status = -1;

}
else if(visit[point] == 1)
{
//when start and end node are not same then
//allow to visit same node more than once
return;
}
//Set visited status 1
visit[point]=1;

//Get the address of first edge of  current node
AjlistNode  temp=node[point].next;

while(temp!=null)
{
if( status != -1)
{
detectCycle(temp.id,visit);

}else
{
break;
}
//visit next edge
temp=temp.next;
}
}
}
//method which are manage finding and detecting cycle operation
public void checkCycle()
{

if(node==null)
{
System.out.println("Empty Graph");
return;
}

printGraph();

//This are storing the information about visiting node status
int []visit=new int[size];

int test=0;

while(test < size)
{
//Set all visit node as zero
for(int index=0;index<size;index++)
{
visit[index]=0;
}
//set instance status
status = test;

detectCycle(test,visit);

if(status==-1)
{
break;
}

test++;
}
if(status==-1)
{
System.out.println("\n Detect Cycle");
}else
{
System.out.println("\n No Cycle");
}
}

public static void main(String[] args)
{
int totalNode=6;

MyGraph g=new MyGraph(totalNode);
g.setData();
//Connected two node with Edges

g.checkCycle();

//Case two
g.checkCycle();

}
}``````

#### Output

``````Adjacency list of vertex 0 : 1 3
Adjacency list of vertex 1 : 2
Adjacency list of vertex 2 : 5
Adjacency list of vertex 3 : 4
Adjacency list of vertex 4 : 2
Adjacency list of vertex 5 :
No Cycle

Adjacency list of vertex 0 : 1 3
Adjacency list of vertex 1 : 2
Adjacency list of vertex 2 : 5
Adjacency list of vertex 3 : 4
Adjacency list of vertex 4 : 2
Adjacency list of vertex 5 : 1
Detect Cycle
``````
``````#Python program
# Detect Cycle in a Directed Graph
def __init__(self,data):
self.id=data
self.next=None

class Vertices:
def __init__(self,data):
self.data=data
self.next=None

class Graph:
"""Constructor for Graph"""
def __init__(self, size):
self.size=size
self.node=[]
self.status=0

def setData(self):
if(self.size>0 and self.node!=None):
index=0
while(index<self.size):
self.node.append(Vertices(index))
index+=1

#S and E is two nodes
if(self.size>S and self.size>E):

if(self.node[S].next==None):
self.node[S].next=new_edge
else:
temp=self.node[S].next
while(temp.next!=None):
temp=temp.next
temp.next=new_edge
else:
print("Invalid nodes")

def printGraph(self):

if(self.size>0 and self.node!=None):

index=0

while(index<self.size):

print("\nAdjacency list of vertex  {0} :".format(index),end=" ")

temp=self.node[index].next

while temp!=None:

print("  {0}".format(temp.id),end=" ")

temp=temp.next

index+=1

#Detect cycle using DFS
def detectCycle(self, point, visit):

if( self.status != -1):
if(visit[self.status] == 1 and point ==  self.status):
#when visits a node are more than one
#contain cycle
self.status = -1

elif(visit[point] == 1):
#when start and end node are not same then
#allow to visit same node more than once
return

#Set visited status 1
visit[point]=1

#Get the address of first edge of  current node
temp=self.node[point].next

while(temp!=None):
if( self.status != -1):
self.detectCycle(temp.id,visit)

else:
break

#visit next edge
temp=temp.next

#method which are manage finding and detecting cycle operation
def checkCycle(self):

if(self.node==None):
print("Empty Graph")
return

self.printGraph()

#This are storing the information about visiting node status
visit=[0]*self.size

test=0

while(test < self.size):
index=0
while (index<self.size):
visit[index]=0
index+=1

#set instance status
self.status = test

self.detectCycle(test,visit)

if(self.status==-1):
break

test+=1

if(self.status==-1):

print("\n Detect Cycle")
else:
print("\n No Cycle")

def main():
g=Graph(6)
g.setData()
#Connected two node with Edges

g.checkCycle()

#Case two
g.checkCycle()
if __name__=="__main__":
main()``````

#### Output

``````Adjacency list of vertex  0 :   1   3
Adjacency list of vertex  1 :   2
Adjacency list of vertex  2 :   5
Adjacency list of vertex  3 :   4
Adjacency list of vertex  4 :   2
Adjacency list of vertex  5 :
No Cycle

Adjacency list of vertex  0 :   1   3
Adjacency list of vertex  1 :   2
Adjacency list of vertex  2 :   5
Adjacency list of vertex  3 :   4
Adjacency list of vertex  4 :   2
Adjacency list of vertex  5 :   1
Detect Cycle
``````
``````//C# Graph
//Detect Cycle in a Directed Graph
using System;
class AjlistNode
{
public int key;
public AjlistNode next;
public AjlistNode(int key)
{
this.key=key;
this.next=null;
}
}
class Node
{
public int data;
public AjlistNode next;
public Node(int data)
{
this.data=data;
this.next=null;

}
}
class MyGraph
{
//empty array
public Node[]node= new Node[] {};
public int size;
public MyGraph(int size)
{
this.size=size;
node=new Node[size];
}
public void setData()
{
if(size>0 && this.node!=null)
{
for(int index=0;index<size;index++)
{
node[index]=new Node(index);
}

}
}
{
if(this.size>start && this.size>end)
{
AjlistNode newEdge=new AjlistNode(end);

if(node[start].next==null)
{
node[start].next=newEdge;
}else
{
AjlistNode temp=node[start].next;
while(temp.next!=null)
{
temp=temp.next;
}
temp.next=newEdge;
}

}
}
public void printGraph()
{
if(size>0 && node.Length>0 && node!=null)
{
for(int index=0;index<size;index++)
{
Console.Write("\nAdjacency list of vertex {0} :",index);
AjlistNode temp=node[index].next;
while(temp!=null)
{
Console.Write(" "+node[temp.key].data);
temp=temp.next;
}
}
}
}
//Detect cycle using DFS
public void detectCycle(int point,int []visit,ref int status)
{

if( status != -1)
{
if(visit[status] == 1 && point ==  status)
{
//when visits a node are more than one
//contain cycle
status = -1;

}
else if(visit[point] == 1)
{
//when start and end node are not same then
//allow to visit same node more than once
return;
}
//Set visited status 1
visit[point]=1;

//Get the address of first edge of  current node
AjlistNode  temp=node[point].next;

while(temp!=null)
{
if( status != -1)
{
detectCycle(temp.key,visit,ref status);

}else
{
break;
}
//visit next edge
temp=temp.next;
}
}
}
//method which are manage finding and detecting cycle operation
public void checkCycle()
{

if(node==null)
{
Console.WriteLine("Empty Graph");
return;
}

printGraph();

//This are storing the information about visiting node status
int []visit=new int[size];

int test=0,status=0;

while(test < size)
{
//Set all visit node as zero
for(int index=0;index<size;index++)
{
visit[index]=0;
}
//set instance status
status = test;

detectCycle(test,visit,ref status);

if(status==-1)
{
break;
}

test++;
}
if(status==-1)
{
Console.WriteLine("\n Detect Cycle");
}else
{
Console.WriteLine("\n No Cycle");
}
}

}
class Program
{

static void Main(string[] args)
{
//create object
MyGraph g=new MyGraph(6);
g.setData();
//Connected two node with Edges

g.checkCycle();

//Case two
g.checkCycle();
}
}``````

#### Output

``````Adjacency list of vertex 0 : 1 3
Adjacency list of vertex 1 : 2
Adjacency list of vertex 2 : 5
Adjacency list of vertex 3 : 4
Adjacency list of vertex 4 : 2
Adjacency list of vertex 5 :
No Cycle

Adjacency list of vertex 0 : 1 3
Adjacency list of vertex 1 : 2
Adjacency list of vertex 2 : 5
Adjacency list of vertex 3 : 4
Adjacency list of vertex 4 : 2
Adjacency list of vertex 5 : 1
Detect Cycle
``````
``````<?php
/*
* PHP Program
* Detect Cycle in a Directed Graph
*/

class AjlistNode
{
public \$key;
public \$next;
function __construct(\$key)
{
\$this->key=\$key;
\$this->next=NULL;
}
}
class Node
{
public \$data;
public \$next;
function __construct(\$data)
{
\$this->data=\$data;
\$this->next=NULL;

}
}
class MyGraph
{

public \$node;
public \$size;
function __construct(\$size)
{
\$this->size=\$size;
\$this->node=[];  //empty array
}
public function setData()
{
if(\$this->size>0)
{
for(\$index=0;\$index<\$this->size;\$index++)
{
\$this->node[\$index]=new Node(\$index);
}

}
}
{
if(\$this->size > \$start && \$this->size>\$end)
{
\$newEdge=new AjlistNode(\$end);
if(\$this->node[\$start]->next==NULL)
{
\$this->node[\$start]->next=\$newEdge;
}
else
{

\$temp=\$this->node[\$start]->next;
while(\$temp->next!=NULL)
{
\$temp=\$temp->next;
}
\$temp->next= \$newEdge;
}
}
}
public function printGraph()
{
if(\$this->size>0 && count(\$this->node)>0 && \$this->node!=NULL)
{
for(\$index=0;\$index<\$this->size;\$index++)
{
echo ("\nAdjacency list of vertex ".\$index." : ");
\$temp=\$this->node[\$index]->next;
while(\$temp!=NULL)
{
echo (" ".\$this->node[\$temp->key]->data);
\$temp=\$temp->next;
}
}
}
}

public function detect_cycle(\$point,\$visit,& \$status)
{

if(\$status!=-1)
{
if(\$visit[\$status]==1 && \$point == \$status)
{
\$status=-1;
}else if(\$visit[\$point]==1)
{
return;
}
\$visit[\$point]=1;
\$temp=\$this->node[\$point]->next;
while(\$temp!=NULL)
{
if(\$status!=-1)
{
\$this->detect_cycle(\$temp->key,\$visit,\$status);

}else
{
break;
}

\$temp=\$temp->next;
}
}
}
public function check_cycle()
{

if(\$this->node==NULL)
{
echo ("Empty Graph\n");
return;
}
\$this->printGraph();
\$visit=[];
\$test=0;
\$status=0;
while(\$test < \$this->size)
{
\$status=\$test;
for(\$index=0;\$index<\$this->size;\$index++)
{
\$visit[\$index]=0;
}
\$this->detect_cycle(\$test,\$visit,\$status);
if(\$status==-1)
{
break;
}
\$test++;
}
if(\$status==-1)
{

echo ("\n Detect Cycle\n");
}else
{
echo ("\n No Cycle\n");
}
}

}

function main()
{
//create object
\$g=new MyGraph(6);
\$g->setData();

//Connected two node with Edges

\$g->check_cycle();

//Case two
\$g->check_cycle();

}
main();
?>``````

#### Output

``````Adjacency list of vertex 0 :  1 3
Adjacency list of vertex 1 :  2
Adjacency list of vertex 2 :  5
Adjacency list of vertex 3 :  4
Adjacency list of vertex 4 :  2
Adjacency list of vertex 5 :
No Cycle

Adjacency list of vertex 0 :  1 3
Adjacency list of vertex 1 :  2
Adjacency list of vertex 2 :  5
Adjacency list of vertex 3 :  4
Adjacency list of vertex 4 :  2
Adjacency list of vertex 5 :  1
Detect Cycle
``````

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.