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
Depth First Traversal can be used to detect cycle in a Graph. DFS for a connected graph produces a tree. 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. In the following graph, there are 3 back edges, marked with cross sign. We can observe that these 3 back edges indicate 3 cycles present in the graph.
For a disconnected graph, we get the DFS forrest as output
[ad type=”banner”]. To detect cycle, we can check for cycle in individual trees by checking back edges.To detect a back edge, we can keep track of vertices currently in recursion stack of function for DFS traversal. If we reach a vertex that is already in the recursion stack, then there is a cycle in the tree. The edge that connects current vertex to the vertex in the recursion stack is back edge. We have used recStack[] array to keep track of vertices in the recursion stack.
[pastacode lang=”cpp” manual=”%2F%2F%20A%20C%2B%2B%20Program%20to%20detect%20cycle%20in%20a%20graph%0A%23include%3Ciostream%3E%0A%23include%20%3Clist%3E%0A%23include%20%3Climits.h%3E%0A%20%0Ausing%20namespace%20std%3B%0A%20%0Aclass%20Graph%0A%7B%0A%20%20%20%20int%20V%3B%20%20%20%20%2F%2F%20No.%20of%20vertices%0A%20%20%20%20list%3Cint%3E%20*adj%3B%20%20%20%20%2F%2F%20Pointer%20to%20an%20array%20containing%20adjacency%20lists%0A%20%20%20%20bool%20isCyclicUtil(int%20v%2C%20bool%20visited%5B%5D%2C%20bool%20*rs)%3B%20%20%2F%2F%20used%20by%20isCyclic()%0Apublic%3A%0A%20%20%20%20Graph(int%20V)%3B%20%20%20%2F%2F%20Constructor%0A%20%20%20%20void%20addEdge(int%20v%2C%20int%20w)%3B%20%20%20%2F%2F%20to%20add%20an%20edge%20to%20graph%0A%20%20%20%20bool%20isCyclic()%3B%20%20%20%20%2F%2F%20returns%20true%20if%20there%20is%20a%20cycle%20in%20this%20graph%0A%7D%3B%0A%20%0AGraph%3A%3AGraph(int%20V)%0A%7B%0A%20%20%20%20this-%3EV%20%3D%20V%3B%0A%20%20%20%20adj%20%3D%20new%20list%3Cint%3E%5BV%5D%3B%0A%7D%0A%20%0Avoid%20Graph%3A%3AaddEdge(int%20v%2C%20int%20w)%0A%7B%0A%20%20%20%20adj%5Bv%5D.push_back(w)%3B%20%2F%2F%20Add%20w%20to%20v%E2%80%99s%20list.%0A%7D%0A%20%0A%2F%2F%20This%20function%20is%20a%20variation%20of%20DFSUytil()%20in%20http%3A%2F%2Fwww.geeksforgeeks.org%2Farchives%2F18212%0Abool%20Graph%3A%3AisCyclicUtil(int%20v%2C%20bool%20visited%5B%5D%2C%20bool%20*recStack)%0A%7B%0A%20%20%20%20if(visited%5Bv%5D%20%3D%3D%20false)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%2F%2F%20Mark%20the%20current%20node%20as%20visited%20and%20part%20of%20recursion%20stack%0A%20%20%20%20%20%20%20%20visited%5Bv%5D%20%3D%20true%3B%0A%20%20%20%20%20%20%20%20recStack%5Bv%5D%20%3D%20true%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20Recur%20for%20all%20the%20vertices%20adjacent%20to%20this%20vertex%0A%20%20%20%20%20%20%20%20list%3Cint%3E%3A%3Aiterator%20i%3B%0A%20%20%20%20%20%20%20%20for(i%20%3D%20adj%5Bv%5D.begin()%3B%20i%20!%3D%20adj%5Bv%5D.end()%3B%20%2B%2Bi)%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20(%20!visited%5B*i%5D%20%26%26%20isCyclicUtil(*i%2C%20visited%2C%20recStack)%20)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20return%20true%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20else%20if%20(recStack%5B*i%5D)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20return%20true%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%0A%20%20%20%20%7D%0A%20%20%20%20recStack%5Bv%5D%20%3D%20false%3B%20%20%2F%2F%20remove%20the%20vertex%20from%20recursion%20stack%0A%20%20%20%20return%20false%3B%0A%7D%0A%20%0A%2F%2F%20Returns%20true%20if%20the%20graph%20contains%20a%20cycle%2C%20else%20false.%0A%2F%2F%20This%20function%20is%20a%20variation%20of%20DFS()%20in%20http%3A%2F%2Fwww.geeksforgeeks.org%2Farchives%2F18212%0Abool%20Graph%3A%3AisCyclic()%0A%7B%0A%20%20%20%20%2F%2F%20Mark%20all%20the%20vertices%20as%20not%20visited%20and%20not%20part%20of%20recursion%0A%20%20%20%20%2F%2F%20stack%0A%20%20%20%20bool%20*visited%20%3D%20new%20bool%5BV%5D%3B%0A%20%20%20%20bool%20*recStack%20%3D%20new%20bool%5BV%5D%3B%0A%20%20%20%20for(int%20i%20%3D%200%3B%20i%20%3C%20V%3B%20i%2B%2B)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20visited%5Bi%5D%20%3D%20false%3B%0A%20%20%20%20%20%20%20%20recStack%5Bi%5D%20%3D%20false%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F%2F%20Call%20the%20recursive%20helper%20function%20to%20detect%20cycle%20in%20different%0A%20%20%20%20%2F%2F%20DFS%20trees%0A%20%20%20%20for(int%20i%20%3D%200%3B%20i%20%3C%20V%3B%20i%2B%2B)%0A%20%20%20%20%20%20%20%20if%20(isCyclicUtil(i%2C%20visited%2C%20recStack))%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20true%3B%0A%20%0A%20%20%20%20return%20false%3B%0A%7D%0A%20%0Aint%20main()%0A%7B%0A%20%20%20%20%2F%2F%20Create%20a%20graph%20given%20in%20the%20above%20diagram%0A%20%20%20%20Graph%20g(4)%3B%0A%20%20%20%20g.addEdge(0%2C%201)%3B%0A%20%20%20%20g.addEdge(0%2C%202)%3B%0A%20%20%20%20g.addEdge(1%2C%202)%3B%0A%20%20%20%20g.addEdge(2%2C%200)%3B%0A%20%20%20%20g.addEdge(2%2C%203)%3B%0A%20%20%20%20g.addEdge(3%2C%203)%3B%0A%20%0A%20%20%20%20if(g.isCyclic())%0A%20%20%20%20%20%20%20%20cout%20%3C%3C%20%22Graph%20contains%20cycle%22%3B%0A%20%20%20%20else%0A%20%20%20%20%20%20%20%20cout%20%3C%3C%20%22Graph%20doesn’t%20contain%20cycle%22%3B%0A%20%20%20%20return%200%3B%0A%7D” message=”” highlight=”” provider=”manual”/]Output:
Graph contains cycle
Time Complexity of this method is same as time complexity of DFS traversal which is O(V+E).
[ad type=”banner”]