# detect cycle in directed graph & un-directed graph

• ``````

/**
Undirected Graph : for every visited vertex 'v', if there is an adjacent ‘u’ such that u is already visited and u is not parent of v, then there is a cycle in graph.
Directed Graph : There is a cycle in a graph only if there is a back edge present in the graph. A back edge is an edge that is from a node to itself (selfloop)
or one of its ancestor in the tree produced by DFS.
**/

/*** 有向图中检测环  **/

// This function is a variation of DFSUytil() in http://www.geeksforgeeks.org/archives/18212
bool Graph::isCyclicUtil(int v, bool visited[], bool *recStack)
{
if(visited[v] == false)
{
// Mark the current node as visited and part of recursion stack
visited[v] = true;
recStack[v] = true;

// Recur for all the vertices adjacent to this vertex
list<int>::iterator i;
{
if ( !visited[*i] && isCyclicUtil(*i, visited, recStack) )
return true;
// 已经在已经访问过的节点列表中
else if (recStack[*i])
return true;
}

}
recStack[v] = false;  // remove the vertex from recursion stack
return false;
}

// Returns true if the graph contains a cycle, else false.
// This function is a variation of DFS() in http://www.geeksforgeeks.org/archives/18212
bool Graph::isCyclic()
{
// Mark all the vertices as not visited and not part of recursion
// stack
bool *visited = new bool[V];
bool *recStack = new bool[V];
for(int i = 0; i < V; i++)
{
visited[i] = false;
recStack[i] = false;
}

// Call the recursive helper function to detect cycle in different
// DFS trees
for(int i = 0; i < V; i++)
if (isCyclicUtil(i, visited, recStack))
return true;

return false;
}

// 使用3种颜色数组用来检测环
bool Graph::DFSUtil(int u, int color[])
{
// GRAY :  This vertex is being processed (DFS
//         for this vertex has started, but not
//         ended (or this vertex is in function
//         call stack)
color[u] = GRAY;

// Iterate through all adjacent vertices
list<int>::iterator i;
{
int v = *i;  // An adjacent of u

// If there is
if (color[v] == GRAY)
return true;

// If v is not processed and there is a back
// edge in subtree rooted with v
if (color[v] == WHITE && DFSUtil(v, color))
return true;
}

// Mark this vertex as processed
color[u] = BLACK;

return false;
}

// Returns true if there is a cycle in graph
bool Graph::isCyclic()
{
// Initialize color of all vertices as WHITE
int *color = new int[V];
for (int i = 0; i < V; i++)
color[i] = WHITE;

// Do a DFS traversal beginning with all
// vertices
for (int i = 0; i < V; i++)
if (color[i] == WHITE)
if (DFSUtil(i, color) == true)
return true;

return false;
}

/*** 无向图中检测环  **/
// A recursive function that uses visited[] and parent to detect
// cycle in subgraph reachable from vertex v.
bool Graph::isCyclicUtil(int v, bool visited[], int parent)
{
// Mark the current node as visited
visited[v] = true;

// Recur for all the vertices adjacent to this vertex
list<int>::iterator i;
{
// If an adjacent is not visited, then recur for that adjacent
if (!visited[*i])
{
if (isCyclicUtil(*i, visited, v))
return true;
}
// 访问过的点并且不是当前点的父亲节点
// If an adjacent is visited and not parent of current vertex,
// then there is a cycle.
else if (*i != parent)
return true;
}
return false;
}

// Returns true if the graph contains a cycle, else false.
bool Graph::isCyclic()
{
// Mark all the vertices as not visited and not part of recursion
// stack
bool *visited = new bool[V];
for (int i = 0; i < V; i++)
visited[i] = false;

// Call the recursive helper function to detect cycle in different
// DFS trees
for (int u = 0; u < V; u++)
if (!visited[u]) // Don't recur for u if it is already visited
if (isCyclicUtil(u, visited, -1))
return true;

return false;
}

// A C++ Program to detect cycle in a graph
#include<iostream>
#include <list>
#include <limits.h>

using namespace std;

class Graph
{
int V;    // No. of vertices
bool isCyclicUtil(int v, bool visited[], bool *rs);  // used by isCyclic()
public:
Graph(int V);   // Constructor
void addEdge(int v, int w);   // to add an edge to graph
bool isCyclic();    // returns true if there is a cycle in this graph
};

Graph::Graph(int V)
{
this->V = V;
}

{
}

/** DFS of a graph **/
/** if the graph is connected **/

void Graph::DFSUtil(int v, bool visited[])
{
// Mark the current node as visited and print it
visited[v] = true;
cout << v << " ";

// Recur for all the vertices adjacent to this vertex
list<int>::iterator i;
if (!visited[*i])
DFSUtil(*i, visited);
}

// DFS traversal of the vertices reachable from v. It uses recursive DFSUtil()
void Graph::DFS(int v)
{
// Mark all the vertices as not visited
bool *visited = new bool[V];
for (int i = 0; i < V; i++)
visited[i] = false;

// Call the recursive helper function to print DFS traversal
DFSUtil(v, visited);
}

/** DFS of a graph **/
/** if the graph is composed of multiple connected components **/
void Graph::DFSUtil(int v, bool visited[])
{
// Mark the current node as visited and print it
visited[v] = true;
cout << v << " ";

// Recur for all the vertices adjacent to this vertex
list<int>::iterator i;
if(!visited[*i])
DFSUtil(*i, visited);
}

// The function to do DFS traversal. It uses recursive DFSUtil()
void Graph::DFS()
{
// Mark all the vertices as not visited
bool *visited = new bool[V];
for (int i = 0; i < V; i++)
visited[i] = false;

// Call the recursive helper function to print DFS traversal
// starting from all vertices one by one
for (int i = 0; i < V; i++)
if (visited[i] == false)
DFSUtil(i, visited);
}

/** BFS of a grapth **/

void Graph::BFS(int s)
{
// Mark all the vertices as not visited
bool *visited = new bool[V];
for(int i = 0; i < V; i++)
visited[i] = false;

// Create a queue for BFS
list<int> queue;

// Mark the current node as visited and enqueue it
visited[s] = true;
queue.push_back(s);

// 'i' will be used to get all adjacent vertices of a vertex
list<int>::iterator i;

while(!queue.empty())
{
// Dequeue a vertex from queue and print it
s = queue.front();
cout << s << " ";
queue.pop_front();

// Get all adjacent vertices of the dequeued vertex s
// If a adjacent has not been visited, then mark it visited
// and enqueue it
{
if(!visited[*i])
{
visited[*i] = true;
queue.push_back(*i);
}
}
}
}

/** detect cycle using the DFS method **/

// This function is a variation of DFSUytil() in http://www.geeksforgeeks.org/archives/18212
bool Graph::isCyclicUtil(int v, bool visited[], bool *recStack)
{
if(visited[v] == false)
{
// Mark the current node as visited and part of recursion stack
visited[v] = true;
recStack[v] = true;

// Recur for all the vertices adjacent to this vertex
list<int>::iterator i;
{
if ( !visited[*i] && isCyclicUtil(*i, visited, recStack) )
return true;
else if (recStack[*i])
return true;
}

}
recStack[v] = false;  // remove the vertex from recursion stack
return false;
}

// Returns true if the graph contains a cycle, else false.
// This function is a variation of DFS() in http://www.geeksforgeeks.org/archives/18212
bool Graph::isCyclic()
{
// Mark all the vertices as not visited and not part of recursion
// stack
bool *visited = new bool[V];
bool *recStack = new bool[V];
for(int i = 0; i < V; i++)
{
visited[i] = false;
recStack[i] = false;
}

// Call the recursive helper function to detect cycle in different
// DFS trees
for(int i = 0; i < V; i++)
if (isCyclicUtil(i, visited, recStack))
return true;

return false;
}``````

• @fight.for.dream is it an interview question given in Google?

• Wow, long code.. :stuck_out_tongue: This code is suspiciously similar to http://www.geeksforgeeks.org/detect-cycle-in-a-graph/ and http://www.geeksforgeeks.org/detect-cycle-direct-graph-using-colors/

I was just wondering, in case of Undirected graphs can't we simply use Disjoint Set Union policy based structures to keep track of connected components? Two different unprocessed elements having same parents would mean a cycle exists.

• @babhishek21 yes, right