Detecting cycle in graph is one of use case for  depth first traversal. In this discussion we will study how to use DFS for detecting cycle in undirected graph. For example in given below graph has cycle 0-1-2-0.

how to detect cycle in undirected graph using depth first search

Let us understand a simple concept: “Back Edge”

Edge ( U,V) ,where U and V are nodes/vertices of graph, is called “Back Edge” if 

  • V is already visited and and V is ancestor of U. 
  • For example if we start visiting from 0 ( in above graph) using depth first then 0 is marked as visited.  Now the nodes which are reachable from 0 are 1 and 2. Let us visit node 1 and marked it visited.

cyclgm

 

Now we are at node 1. the only node reachable from 1 is 2, so let us visit node 2 and mark it visited. Again we are at node 2. The nodes which are reachable from 2 are 1,3,5,0. If we visit node 0 , in this case the edge ( from 2(U) to 0(V) ) is back edge because  V is already visited and V(0) is ancestor of U(2), in depth first tree ( 0>>1>>2>>0).

how to detect cycle in undirected graph using depth first search

So if a graph ( directed or undirected ) has back edge then graph must contain cycle.

If we detect any back edge during depth first traversal in graph then it is enough to prove that graph is containing cycle in it.

C implementation of above logic:

#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];
int parent[nodes];
bool checkBackEdge (int u, int v);
bool
DFSAll (int G[nodes][nodes])
{
  int i = 0;
  for (i = 0; i < nodes; i++)
    {
      colorOfNode[i] = white;
      parent[i] = -1;
    }
  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))
	{
	  parent[v] = u;
	  // then visit vertex v
	  if (DFSDetectCycle (G, v))
	    {
	      return true;
	    }
	}
      // cycle found
      else if (G[u][v] && colorOfNode[v] == gray)
	{
	  if (checkBackEdge (u, v))
	    return true;
	}
    }
  colorOfNode[u] = black;	// finished node
  return false;
}

bool
checkBackEdge (int u, int v)
{
  if (parent[u] != v)
    return true;
  else
    return false;
}

// main
int
main ()
{
  int G1[nodes][nodes] = { {0, 1, 1, 0, 0, 0},
  {1, 1, 0, 0, 0, 0},
  {0, 0, 0, 1, 0, 1},
  {0, 0, 1, 0, 0, 0},
  {0, 0, 0, 1, 0, 0},
  {0, 0, 1, 0, 0, 0}
  };
  int G2[nodes][nodes] = { {0, 1, 0, 0, 0, 0},
  {1, 0, 1, 0, 0, 0},
  {0, 1, 0, 1, 0, 0},
  {0, 0, 1, 0, 0, 1},
  {0, 0, 0, 0, 0, 1},
  {0, 0, 0, 1, 1, 0}
  };

  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");
  return 0;
}


Related Contents to follow