Posted on by Kalkicode
Code Graph

Detect Cycle in an Undirected Graph

The problem tackled in this context is about detecting cycles in an undirected graph. A cycle in a graph occurs when there is a closed path formed by traversing a sequence of vertices and edges, where the starting and ending vertices are the same. Detecting cycles in a graph is crucial in various applications like dependency analysis, deadlock detection, and resource allocation.

Problem Statement and Description

The objective is to develop a C program that can identify cycles in an undirected graph. Given a graph with vertices and edges, the program should determine whether the graph contains any cycles.

Example

Consider the following undirected graph:

Detect Cycle in an Undirected Graph

Idea to Solve the Problem

The idea to detect cycles in an undirected graph involves performing a depth-first search (DFS) traversal on the graph. During the traversal, we keep track of the vertices we visit and check if we encounter a vertex that has already been visited. If we do, it indicates the presence of a cycle.

Standard Pseudocode

procedure detect_cycle(graph):
    initialize an array 'visited' to keep track of visited vertices
    initialize a variable 'status' to indicate cycle presence (initially 0)

    for each vertex in graph:
        if vertex is not visited:
            perform DFS from the vertex and mark visited vertices
            if a visited vertex is encountered during DFS:
                set status to indicate cycle presence
                break
    
    if status is 1:
        print "Yes, cycle detected"
    else:
        print "No, no cycle detected"

Algorithm Explanation

  1. The detect_cycle function takes the graph as input.
  2. It initializes an array called visited to keep track of visited vertices.
  3. It also initializes a variable status to 0, which indicates no cycle has been found.
  4. For each vertex in the graph, it checks if the vertex has been visited.
  5. If the vertex has not been visited, it performs a DFS from that vertex, marking visited vertices.
  6. During DFS, if a visited vertex is encountered, it sets status to 1, indicating a cycle has been found.
  7. After the loop, it checks the value of status to determine whether a cycle was detected or not.

Code Solution

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

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

struct Graph
{
  //node key value
  int data;
  struct AjlistNode*next;
};
void setData(struct Graph *);
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");
  }
}

void connect_edge(struct Graph*node, int V ,int E)
{

    // create Adjacency node
  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
    {
            //Add node at last
      while(temp->next!=NULL)
      {
        temp=temp->next;
      }      
      temp->next=newEdge;          
    }
  }else
  {
    printf("\n Memory overflow");

  }
}
//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)
  {

    connect_edge(node,V,E);
    connect_edge(node,E,V);

  }else
  {
        //not valid Vertices
    printf("Invalid Node Vertices %d  %d", V,E);
  }
}
//Display Adjacency list of vertex
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)
{
  if(visit[point]>=1)
  {

    visit[point]=visit[point]+1;

    return;
  }
  visit[point]=1;
  struct AjlistNode *temp=node[point].next;
  int counter=0;
  while(temp!=NULL)
  {
    counter++;
    detect_cycle(temp->vId,visit,node); 
    temp=temp->next;
  }
  
  if(counter>0)
  {
    visit[point]=visit[point]-counter;
    if(visit[point]<0)
    {
      visit[point]=-visit[point];
    }
  }


}
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;

  detect_cycle(test,visit,node);

  printf("\n result : ");
  for(int index=0;index<size;index++)
  {

    if(index==0&&visit[index]==1)
    {
      //This are start vertex
      continue;
    }
    if(visit[index]>0)
    {
      status=1;
      break;
    }
  }
  if(status==1)
  {
    printf("Yes\n");
  }else
  {
    printf("No\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

    addEdge(node,0,1);
    addEdge(node,0,2);
    addEdge(node,1,3);
    addEdge(node,1,4);

    addEdge(node,2,5);

    check_cycle(node);

    addEdge(node,5,4);

    //Case two
    check_cycle(node);
  }  

  return 0;
}

Output

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

 Adjacency list of vertex 0  :  1  2
 Adjacency list of vertex 1  :  0  3  4
 Adjacency list of vertex 2  :  0  5
 Adjacency list of vertex 3  :  1
 Adjacency list of vertex 4  :  1  5
 Adjacency list of vertex 5  :  2  4
 result : Yes
//C++ program
//Detect Cycle in a Undirected 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 addEdge(int,int);
	void printGraph();
	void check_cycle();
	void detect_cycle(int ,int []);
	void connect(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 ::connect(int V ,int E)
{
    //add edge form V to E
    //V and E is Node location
    //first create Adjacency node
	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
		{
            //Add node at last
			while(temp->next!=NULL)
			{
				temp=temp->next;
			}      
			temp->next=newEdge;          
		}
	}

}


void Graph ::addEdge(int V ,int E)
{
    //add edge form V to E
    //V and E is Node location
	if(V<size && E <size)
	{
		connect(V,E);
		if(V==E)
        {   //self loop
        	return;
        }
        connect(E,V);

    }else
    {
        //not valid Vertices
    	cout<<"Invalid Node Vertices "<< V<<" "<<E;
    }
}

//Display Adjacency list of vertex
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[])
{

	if(visit[point]>=1)
	{

		visit[point]=visit[point]+1;

		return;
	}
	visit[point]=1;
	struct AjlistNode *temp=node[point].next;
	int counter=0;
	while(temp!=NULL)
	{
		counter++;
		detect_cycle(temp->vId,visit); 
		temp=temp->next;
	}

	if(counter>0)
	{
		visit[point]=visit[point]-counter;
		if(visit[point]<0)
		{
			visit[point]=-visit[point];
		}
	}
}
//method which are manage finding and detecting cycle operation
void Graph:: check_cycle()
{

	if(node==NULL)
	{
		cout<<("Empty Graph\n");
		return;
	}
	printGraph();
	
	int test=0,status=0;

	int *visit= new int[size];
    for (int i = 0; i < size; ++i)
    {
    	visit[i]=0;
    }
	detect_cycle(test,visit);
    
	cout<<"\n result : ";
	for(int index=0;index<size;index++)
	{

		if(index==0&&visit[index]==1)
		{
	      //This are start vertex
			continue;
		}
		if(visit[index]>0)
		{
			status=1;
			break;
		}
	}
	if(status==1)
	{
		cout<<" Yes\n";
	}else
	{
		cout<<" No \n";
	}
}

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

	g.addEdge(0,1);
	g.addEdge(0,2);
	g.addEdge(1,3);
	g.addEdge(1,4);

	g.addEdge(2,5);

	g.check_cycle();

	g.addEdge(5,4);

        //Case two
	g.check_cycle();

	return 0;
}

Output

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

 Adjacency list of vertex 0 : 1 2
 Adjacency list of vertex 1 : 0 3 4
 Adjacency list of vertex 2 : 0 5
 Adjacency list of vertex 3 : 1
 Adjacency list of vertex 4 : 1 5
 Adjacency list of vertex 5 : 2 4
 result :  Yes
//Java program
//Detect Cycle in a Undirected 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[];

    MyGraph(int size)
    {
        //set value
        this.size = size;
        node = new Vertices[size];
        
    }

    //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].data=index;//set your data
                node[index].next=null;
            }
        }
    }
    //connect two nodes
    public void connect(int start,int end)
    {
        AjlistNode newEdge=new AjlistNode();
            newEdge.id=end;//end node
            newEdge.next=null;
            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;
            }
    }
    //Add edge at the end
    public void addEdge(int start,int end)
    {
        if(start < size && end < size && node != null)
        {
           connect(start,end);
           if(start==end)
           {
            //self loop
            return;
           }
           connect(end,start);
        }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(visit[point] >= 1)
        {

            visit[point]=visit[point]+1;
            return;
        }
        visit[point]=1;

        AjlistNode  temp=node[point].next;
        int counter=0;
        while(temp!=null)
        {
            counter++;
            detectCycle(temp.id,visit); 
            temp=temp.next;
        }

        if(counter>0)
        {
            visit[point] = visit[point]-counter;

            if(visit[point]<0)
            {
                visit[point]=-visit[point];
            }
        }
    }
    //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];
        
        for(int index=0;index < size; index++)
        {
           visit[0]=0;
        }
        detectCycle(0,visit); 

        int test=0,status=0;

        System.out.print("\nresult : ");

        for(int index=0;index < size; index++)
        {

            if(index==0 && visit[index]==1)
            {
                //This are start vertex
                continue;
            }
            if(visit[index]>0)
            {
                status=1;
                break;
            }
        }
        if(status==1)
        {
            System.out.println("Yes");
        }else
        {
            System.out.println("No ");
        }
    }

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

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

        g.addEdge(0,1);
        g.addEdge(0,2);
        g.addEdge(1,3);
        g.addEdge(1,4);

        g.addEdge(2,5);

        g.checkCycle();

        g.addEdge(5,4);

        //Case two
        g.checkCycle();

    }
}

Output

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

Adjacency list of vertex 0 : 1 2
Adjacency list of vertex 1 : 0 3 4
Adjacency list of vertex 2 : 0 5
Adjacency list of vertex 3 : 1
Adjacency list of vertex 4 : 1 5
Adjacency list of vertex 5 : 2 4
result : Yes
#Python program
#Detect Cycle in a Undirected Graph
class AjLinkeNode:
  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=[]
    

  def setData(self):
    if(self.size>0 and self.node!=None):
      index=0
      while(index<self.size):
        self.node.append(Vertices(index))
        index+=1
  #connect two node with  edge
  def connect(self,start,end):
    new_edge=AjLinkeNode(end)
    if(self.node[start].next==None):
      self.node[start].next=new_edge
    else:
      temp=self.node[start].next
      while(temp.next!=None):
        temp=temp.next
      temp.next=new_edge      
  #add edge
  def addEdge(self,start,end):

    #start,end is two nodes
    if(self.size>start and self.size>start):
      
      self.connect(start,end)
      if(start == end):
        return
      self.connect(end,start)  

    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(visit[point] >= 1):
      visit[point]=visit[point]+1
      return
    
    visit[point]=1

    temp=self.node[point].next
    counter=0
    while(temp!=None):
      counter+=1
      self.detectCycle(temp.id,visit) 
      temp=temp.next
    

    if(counter>0):
      visit[point] = visit[point]-counter

      if(visit[point]<0):
        visit[point]=-visit[point]
        
    

    
    #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

    self.detectCycle(0,visit); 
    status=0
    index=0
    print("\nresult : ",end="")
    while(index < self.size):
      
      if(index==0 and visit[index]==1):
        index+=1
        #This are start vertex
        continue
      
      if(visit[index]>0):
        status=1
        break
          
      index+=1
    
    if(status==1):

      print("Yes")
    else:
      print("No")
      
    
        
    
def main():
  g=Graph(6)
  g.setData() 
  #Connected two node with Edges

  g.addEdge(0,1)
  g.addEdge(0,2)
  g.addEdge(1,3)
  g.addEdge(1,4)

  g.addEdge(2,5)

  g.checkCycle()

  g.addEdge(5,4)

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

Output

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

Adjacency list of vertex  0 :   1   2 
Adjacency list of vertex  1 :   0   3   4 
Adjacency list of vertex  2 :   0   5 
Adjacency list of vertex  3 :   1 
Adjacency list of vertex  4 :   1   5 
Adjacency list of vertex  5 :   2   4 
result : Yes
//C# Graph 
//Detect Cycle in a Undirected 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];
	}
	//set initial node value
	public void setData()
	{
		if(node == null)
		{
			Console.WriteLine("\nEmpty Graph");
		}else
		{
			for(int index = 0; index < size; index++)
			{
				// avoid java.lang.nullPointerException
				node[index]=new Node(index); 

			}
		}
	}
	//connect two nodes
	public void connect(int start,int 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;
		}
	}
	//Add edge at the end
	public void addEdge(int start,int end)
	{
		if(start < size && end < size && node != null)
		{
			connect(start,end);
			if(start==end)
			{
				//self loop
				return;
			}
			connect(end,start);
		}else{
			Console.WriteLine("\nEmpty Graph");
		}
	}

	public void printGraph()
	{

		if(size>0 && node!=null)
		{
			for(int index=0;index<size;index++)
			{
				Console.Write("\nAdjacency list of vertex "+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)
	{

		if(visit[point] >= 1)
		{
			visit[point]=visit[point]+1;
			return;
		}
		visit[point]=1;

		AjlistNode  temp=node[point].next;
		int counter=0;
		while(temp!=null)
		{
			counter++;
			detectCycle(temp.key,visit); 
			temp=temp.next;
		}

		if(counter>0)
		{
			visit[point] = visit[point]-counter;

			if(visit[point]<0)
			{
				visit[point]=-visit[point];
			}
		}
	}
	//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];

		for(int index=0;index < size; index++)
		{
			visit[0]=0;
		}
		detectCycle(0,visit); 

		int status=0;

		Console.Write("\nresult : ");

		for(int index=0;index < size; index++)
		{
			
			if(index==0 && visit[index]==1)
			{
				//This are start vertex
				continue;
			}
			if(visit[index]>0)
			{
				status=1;
				break;
			}
		}
		if(status==1)
		{
			Console.WriteLine("Yes");
		}else
		{
			Console.WriteLine("No ");
		}
	}

}
class Program
{

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



		g.addEdge(0,1);
		g.addEdge(0,2);
		g.addEdge(1,3);
		g.addEdge(1,4);

		g.addEdge(2,5);

		g.checkCycle();

		g.addEdge(5,4);

		//Case two
		g.checkCycle();

	}
}

Output

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

Adjacency list of vertex 0 : 1 2
Adjacency list of vertex 1 : 0 3 4
Adjacency list of vertex 2 : 0 5
Adjacency list of vertex 3 : 1
Adjacency list of vertex 4 : 1 5
Adjacency list of vertex 5 : 2 4
result : Yes
<?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);
            }

        }
    }
    public function connect($start,$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 addEdge($start,$end)
    {
        if($this->size > $start && $this->size>$end)
        {
            $this->connect($start,$end);
            if($start==$end)
            {
                //self loop 
                return;
            }
            $this->connect($end,$start);
        }
        else
        {
            echo "\n Invalid node";
        }
    }
    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)
    {

        if($visit[$point] >= 1)
        {

            $visit[$point]=$visit[$point]+1;
            return;
        }
        $visit[$point]=1;

        $temp=$this->node[$point]->next;
        $counter=0;
        while($temp!=null)
        {
            $counter++;
            $this->detect_cycle($temp->key,$visit); 
            $temp=$temp->next;
        }

        if($counter>0)
        {
            $visit[$point] = $visit[$point]-$counter;

            if($visit[$point]<0)
            {
                $visit[$point]=-$visit[$point];
            }
        }
    }
    public function check_cycle()
    {

        if($this->node==null)
        {
            echo ("Empty Graph");
            return;
        }

        $this->printGraph();

        //This are storing the information about visiting node status
        $visit=[];
        
        for($index=0;$index < $this->size; $index++)
        {
         $visit[$index]=0;
     }
     $this->detect_cycle(0,$visit); 

     $test=0;
     $status=0;

     echo ("\nResult : ");

     for($index=0; $index < $this->size; $index++)
     {

        if($index==0 && $visit[$index]==1)
        {
                //This are start vertex
            continue;
        }
        if($visit[$index]>0)
        {
            $status=1;
            break;
        }
    }
    if($status==1)
    {
        echo ("Yes\n");
    }else
    {
        echo ("No\n");
    }
}

}


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

    //Connected two node with Edges
    $g->addEdge(0,1);
    $g->addEdge(0,2);
    $g->addEdge(1,3);
    $g->addEdge(1,4);

    $g->addEdge(2,5);

    $g->check_cycle();

    $g->addEdge(5,4);

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

}
main();
?>

Output

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

Adjacency list of vertex 0 :  1 2
Adjacency list of vertex 1 :  0 3 4
Adjacency list of vertex 2 :  0 5
Adjacency list of vertex 3 :  1
Adjacency list of vertex 4 :  1 5
Adjacency list of vertex 5 :  2 4
Result : Yes

Time Complexity

  • The DFS traversal for each vertex takes O(V + E) time, where V is the number of vertices and E is the number of edges.

Comment

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.

New Comment