C Program to Detect Cycle in a Directed Graph
Given a directed graph, check whether the graph contains a cycle or not. Your function should return true if the given graph contains at least one cycle, else return false. For example, the following graph contains three cycles 0->2->0, 0->1->2->0 and 3->3, so your function must return true.
Recommended: Please solve it on “PRACTICE” first, before moving on to the solution.
C++
// A C++ Program to detect cycle in a graph #include <iostream> #include <limits.h> #include <list> using namespace std; class Graph { int V; // No. of vertices list< int >* adj; // Pointer to an array containing adjacency lists 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; adj = new list< int >[V]; } void Graph::addEdge( int v, int w) { adj[v].push_back(w); // Add w to v’s list. } // This function is a variation of DFSUytil() // in https:// www.w3wiki.net/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; for (i = adj[v].begin(); i != adj[v].end(); ++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 https:// www.w3wiki.net/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 ; } int main() { // Create a graph given in the above diagram Graph g(4); g.addEdge(0, 1); g.addEdge(0, 2); g.addEdge(1, 2); g.addEdge(2, 0); g.addEdge(2, 3); g.addEdge(3, 3); if (g.isCyclic()) cout << "Graph contains cycle" ; else cout << "Graph doesn't contain cycle" ; return 0; } |
Output:
Graph contains cycle
Please refer complete article on Detect Cycle in a Directed Graph for more details!