how to detect cycle in directed graph using depth first search.Detecting cycle in directed graph using depth first traversal is one of use case of DFS. for example in below example directed graph there are two cycles in it, one is 0>2>3>0 and second one is 2>3>4>5>2.

how to detect cycle in directed graph using depth first search

how to detect cycle in directed graph using depth first search

┬áThe below implementation of cycle detection in directed graph is using the fact “During dfs if we found a vertex which is already on the stack that means there is loop”. The unvisited node is colored white and the nodes which are on the stack is colored with gray. The finished node is colored black.

#include<stdio.h>
#include<stdbool.h>

#define nodes 6
#define white 0
#define gray 1
#define black 2

int G[nodes][nodes];

bool DFSDetectCycle (int G[nodes][nodes], int u);
int colorOfNode[nodes];

// with cycle 
		      // 0  1  2  3  4  5
int G1[nodes][nodes] = {{0, 0, 1, 0, 0, 0}, // 0
			{1, 0, 0, 0, 1, 0}, // 1
			{0, 0, 0, 1, 0, 0}, // 2
			{1, 0, 0, 0, 1, 0}, // 3
			{0, 0, 0, 0, 0, 1}, // 4
			{0, 0, 1, 0, 0, 0}};// 5

// with no cycle 
		      // 0  1  2  3  4  5
int G2[nodes][nodes] = { {0, 0, 1, 0, 0, 0},// 0
			{1, 0, 0, 0, 1, 0},// 1
			{0, 0, 0, 1, 0, 0},// 2
			{0, 0, 0, 0, 1, 0},// 3
			{0, 0, 0, 0, 0, 0},// 4
			{0, 0, 1, 0, 0, 0}};// 5

int G3[nodes][nodes] = { {0, 0, 0, 0, 0, 0},
{1, 0, 1, 1, 0, 0},
{0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 1},
{1, 0, 1, 0, 0, 0},
{0, 1, 0, 0, 0, 0}
};

bool DFSAll (int G[nodes][nodes])
{
  int i = 0;
  for (i = 0; i < nodes; i++)
    {
      colorOfNode[i] = white;
    }
  for (i = 0; i < nodes; i++)
    {
      if (colorOfNode[i] == white)
	if (DFSDetectCycle (G, i))
	  {
	    return true;
	  }
    }
  printf ("\n");
  return false;
}

bool DFSDetectCycle (int G[nodes][nodes], int u)
{
  // color veterx u gray
  colorOfNode[u] = gray;

  // explore adjacent vertices of u
  int v = 0;
  for (v = 0; v < nodes; v++)
    {
      // if vertex v is not visited
      if (G[u][v] && (colorOfNode[v] == white))
	{
	  // then visit vertex v 
	  if (DFSDetectCycle (G, v))
	    {
	      printf ("%d-", v);
	      return true;
	    }
	}
      // cycle found
      else if (G[u][v] && colorOfNode[v] == gray)
	{
	  printf ("%d-", v);
	  return true;
	}
    }
  colorOfNode[u] = black;
  return false;
}

// main
int main ()
{
  if (DFSAll (G1))
    printf ("cycle detected in G1\n");
  else
    printf ("no cycle detected in G1\n");
  if (DFSAll (G2))
    printf ("cycle detected in G2\n");
  else
    printf ("no cycle detected in G2\n");
  if (DFSAll (G3))
    printf ("cycle detected in G3\n");
  else
    printf ("no cycle detected in G3\n");
  return 0;
}


Related Contents to follow