# how to detect cycle in undirected graph using depth first search

*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.*

*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.*

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

## Leave a Reply