Cycle Detection in a Directed Graph in C++

In this tutorial, we will learn about Cycle Detection in a Directed Graph in C++. Basically, we will use the DFS traversal approach for detecting the cycle in a graph.

We will also see the example to understand the concept in a better way.

Cycle Detection in a Graph

A graph contains a cycle if and only if there is a Back Edge present in a graph. A back edge is an edge that forms the node to itself and one of its ancestor or parents in a DFS tree.

Now, let’s see an example,

Cycle Detection in a Directed Graph in C++

So, in the above example, we can see the back edges in dfs tree. Hence the graph contains a cycle if there are any back edges in dfs tree.

Let’s see the approach,

1.Initially we take the 3 Sets(White,Black and Grey) and stored all the nodes in white set.
2.Then select a node from white set, then remove it from white set and put into the grey set and then perform DFS traversal.
3.During traversal, for every neighbouring node which is present in white set, move it from white set to grey set.
4.During DFS traversal if we find any neighbouring node which is present in a grey set, Hence cycle is present.
5.During traversal, put a node into the black set if it has no more neighbouring nodes present in white set.

Let’s see the pseudo code,

CycleDetect(G,u){
put u into the grey set;
for every v of adj[u] do
    if (v present in white set) then do
       CycleDetect(G,v);
    if (v present in grey set) then do
       print " cycle is present ";
//after traverse all its neighbouring node put the node into the black set
put u into the black set;
}

Here, we will see the code implementation to detect the cycle in a graph.

#include<iostream>
#include<bits/stdc++.h>
using namespace std;
set<int>white;//white container
set<int>grey;//grey container
set<int>black;//black container
int flag=0;
void edge(vector<int>adj[],int u,int v){
  adj[u].push_back(v);
}

//function to detect the cycle in graph
void CycleDetect(int u,vector<int>adj[]){
    white.erase(u);//remove from the white set
    grey.insert(u);//put into the grey set
    for(int i=0;i<adj[u].size();i++){
      if(white.find(adj[u][i])!=white.end())
      {
      CycleDetect(adj[u][i],adj);
      	}
      if(grey.find(adj[u][i])!=grey.end()){ //check if its is present or not in grey set
        flag=1;
      }
    }
    black.insert(u);//put into the black set
    grey.erase(u);//remove from the grey set
}

int main(){
  vector<int>adj[5];//vector of array to store the graph
  
  //input for edges
  edge(adj,0,2);
  edge(adj,0,1);
  edge(adj,1,3);
  edge(adj,2,0);
  edge(adj,3,3);
  edge(adj,2,3);
  edge(adj,2,4);
  for(int i=0;i<5;i++){
  	white.insert(i);
  }
  CycleDetect(0,adj);
  if(flag==0)cout<<"Graph does not contain cycle"<<endl;
  else
  cout<<"Graph contain cycle"<<endl;
  return 0;
}

Output

Graph contain cycle

We hope you have got a clear concept of how to do Cycle Detection in a Directed Graph in C++.

You may also learn,

Breadth first search (BFS) and Depth first search (DFS) for a Graph in C++

Minimum Spanning Tree for Graph in C++

Dijkstra’s shortest path algorithm in C++

Leave a Reply

Your email address will not be published. Required fields are marked *