{"id":25931,"date":"2017-10-25T21:48:42","date_gmt":"2017-10-25T16:18:42","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=25931"},"modified":"2017-10-25T21:48:42","modified_gmt":"2017-10-25T16:18:42","slug":"detect-cycle-directed-graph-2","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/detect-cycle-directed-graph-2\/","title":{"rendered":"Detect Cycle in a Directed Graph"},"content":{"rendered":"<p>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.<span id=\"more-18516\"><\/span> For example, the following graph contains three cycles 0->2->0, 0->1->2->0 and 3->3, so your function must return true<\/p>\n<p>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 <a href=\"http:\/\/en.wikipedia.org\/wiki\/Depth-first_search#Output_of_a_depth-first_search\">back edge<\/a> 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.<\/p>\n<p>For a disconnected graph, we get the DFS forrest as output<\/p>\n[ad type=\u201dbanner\u201d]. To detect cycle, we can check for cycle in individual trees by checking back edges.<\/p>\n<p>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.<\/p>\n[pastacode lang=\u201dcpp\u201d manual=\u201d%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\u2019t%20contain%20cycle%22%3B%0A%20%20%20%20return%200%3B%0A%7D\u201d message=\u201d\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n<p><strong>Output:<\/strong><\/p>\n<pre>Graph contains cycle<\/pre>\n<p>Time Complexity of this method is same as time complexity of <a href=\"http:\/\/www.geeksforgeeks.org\/archives\/18212\">DFS traversal<\/a> which is O(V+E).<\/p>\n[ad type=\u201dbanner\u201d]\n","protected":false},"excerpt":{"rendered":"<p>Detect Cycle in a Directed Graph &#8211; Graph Algorithms &#8211; Given a directed graph, check whether the graph contains a cycle or not.<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[69969,74168,73906],"tags":[76188,76186,76185,76184,76189,76183,76187,76190],"class_list":["post-25931","post","type-post","status-publish","format-standard","hentry","category-algorithm","category-dfs-and-bfs","category-graph-algorithms","tag-detect-cycle-in-a-graph-c-code","tag-detect-cycle-in-directed-graph-c","tag-detect-cycle-in-directed-graph-in-c","tag-detect-cycle-in-directed-graph-java","tag-detect-cycle-in-graph-using-bfs","tag-detect-cycle-in-undirected-graph","tag-detect-cycle-in-undirected-graph-in-c","tag-find-all-cycles-in-a-directed-graph"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/25931","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/comments?post=25931"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/25931\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=25931"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=25931"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=25931"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}