{"id":27655,"date":"2018-04-09T20:21:02","date_gmt":"2018-04-09T14:51:02","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=27655"},"modified":"2018-09-14T18:50:05","modified_gmt":"2018-09-14T13:20:05","slug":"detect-cycle-directed-graph-using-colors","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/detect-cycle-directed-graph-using-colors\/","title":{"rendered":"Detect Cycle in a directed graph using colors"},"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. 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><strong>Solution<\/strong><br \/>\nDepth 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><img fetchpriority=\"high\" decoding=\"async\" class=\"aligncenter size-full wp-image-27676\" src=\"https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2017\/06\/DFS-1.png\" alt=\"Detect Cycle in a directed graph using colors\" width=\"422\" height=\"181\" srcset=\"https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2017\/06\/DFS-1.png 422w, https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2017\/06\/DFS-1-300x129.png 300w\" sizes=\"(max-width: 422px) 100vw, 422px\" \/><\/p>\n<p>In the <a href=\"http:\/\/www.geeksforgeeks.org\/detect-cycle-in-a-graph\/\">previous post<\/a>, we have discussed a solution that stores visited vertices in a separate array which stores vertices of current recursion call stack.<\/p>\n<p>In this post a different solution is discussed. The solution is from <a href=\"http:\/\/www.amazon.in\/Introduction-Algorithms-Thomas-H-Cormen\/dp\/8120340078\/ref=as_sl_pc_qf_sp_asin_til?tag=geeksforgeeks-21&linkCode=w00&linkId=ECBJHKOAMA4NJO33&creativeASIN=8120340078\">CLRS book<\/a>. The idea is to do DFS of given graph and while doing traversal, assign one of the below three colors to every vertex.<\/p>\n<pre><strong>WHITE<\/strong> : Vertex is not processed yet.  Initially\r\n        all vertices are WHITE.\r\n\r\n<strong>GRAY<\/strong> : Vertex is being processed (DFS for this \r\n       vertex has started, but not finished which means\r\n       that all descendants (ind DFS tree) of this vertex\r\n       are not processed yet (or this vertex is in function\r\n       call stack)\r\n\r\n<strong>BLACK<\/strong> : Vertex and all its descendants are \r\n        processed.\r\n\r\nWhile doing DFS, if we encounter an edge from current \r\nvertex to a GRAY vertex, then this edge is back edge \r\nand hence there is a cycle.\r\n<\/pre>\n<p>Below is C++ implementation based on above idea.<\/p>\n[pastacode lang=\u201dcpp\u201d manual=\u201d%2F%2F%20A%20DFS%20based%20approach%20to%20find%20if%20there%20is%20a%20cycle%0A%2F%2F%20in%20a%20directed%20graph.%20%20This%20approach%20strictly%20follows%0A%2F%2F%20the%20algorithm%20given%20in%20CLRS%20book.%0A%23include%20%3Cbits%2Fstdc%2B%2B.h%3E%0Ausing%20namespace%20std%3B%0A%20%0Aenum%20Color%20%7BWHITE%2C%20GRAY%2C%20BLACK%7D%3B%0A%20%0A%2F%2F%20Graph%20class%20represents%20a%20directed%20graph%20using%0A%2F%2F%20adjacency%20list%20representation%0Aclass%20Graph%0A%7B%0A%20%20%20%20int%20V%3B%20%2F%2F%20No.%20of%20vertices%0A%20%20%20%20list%3Cint%3E*%20adj%3B%20%2F%2F%20adjacency%20lists%0A%20%0A%20%20%20%20%2F%2F%20DFS%20traversal%20of%20the%20vertices%20reachable%20from%20v%0A%20%20%20%20bool%20DFSUtil(int%20v%2C%20int%20color%5B%5D)%3B%0Apublic%3A%0A%20%20%20%20Graph(int%20V)%3B%20%20%2F%2F%20Constructor%0A%20%0A%20%20%20%20%2F%2F%20function%20to%20add%20an%20edge%20to%20graph%0A%20%20%20%20void%20addEdge(int%20v%2C%20int%20w)%3B%0A%20%0A%20%20%20%20bool%20isCyclic()%3B%0A%7D%3B%0A%20%0A%2F%2F%20Constructor%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%0A%2F%2F%20Utility%20function%20to%20add%20an%20edge%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\u2019s%20list.%0A%7D%0A%20%0A%2F%2F%20Recursive%20function%20to%20find%20if%20there%20is%20back%20edge%0A%2F%2F%20in%20DFS%20subtree%20tree%20rooted%20with%20\u2019u\u2019%0Abool%20Graph%3A%3ADFSUtil(int%20u%2C%20int%20color%5B%5D)%0A%7B%0A%20%20%20%20%2F%2F%20GRAY%20%3A%20%20This%20vertex%20is%20being%20processed%20(DFS%0A%20%20%20%20%2F%2F%20%20%20%20%20%20%20%20%20for%20this%20vertex%20has%20started%2C%20but%20not%0A%20%20%20%20%2F%2F%20%20%20%20%20%20%20%20%20ended%20(or%20this%20vertex%20is%20in%20function%0A%20%20%20%20%2F%2F%20%20%20%20%20%20%20%20%20call%20stack)%0A%20%20%20%20color%5Bu%5D%20%3D%20GRAY%3B%0A%20%0A%20%20%20%20%2F%2F%20Iterate%20through%20all%20adjacent%20vertices%0A%20%20%20%20list%3Cint%3E%3A%3Aiterator%20i%3B%0A%20%20%20%20for%20(i%20%3D%20adj%5Bu%5D.begin()%3B%20i%20!%3D%20adj%5Bu%5D.end()%3B%20%2B%2Bi)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20int%20v%20%3D%20*i%3B%20%20%2F%2F%20An%20adjacent%20of%20u%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20If%20there%20is%0A%20%20%20%20%20%20%20%20if%20(color%5Bv%5D%20%3D%3D%20GRAY)%0A%20%20%20%20%20%20%20%20%20%20return%20true%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20If%20v%20is%20not%20processed%20and%20there%20is%20a%20back%0A%20%20%20%20%20%20%20%20%2F%2F%20edge%20in%20subtree%20rooted%20with%20v%0A%20%20%20%20%20%20%20%20if%20(color%5Bv%5D%20%3D%3D%20WHITE%20%26%26%20DFSUtil(v%2C%20color))%0A%20%20%20%20%20%20%20%20%20%20return%20true%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F%2F%20Mark%20this%20vertex%20as%20processed%0A%20%20%20%20color%5Bu%5D%20%3D%20BLACK%3B%0A%20%0A%20%20%20%20return%20false%3B%0A%7D%0A%20%0A%2F%2F%20Returns%20true%20if%20there%20is%20a%20cycle%20in%20graph%0Abool%20Graph%3A%3AisCyclic()%0A%7B%0A%20%20%20%20%2F%2F%20Initialize%20color%20of%20all%20vertices%20as%20WHITE%0A%20%20%20%20int%20*color%20%3D%20new%20int%5BV%5D%3B%0A%20%20%20%20for%20(int%20i%20%3D%200%3B%20i%20%3C%20V%3B%20i%2B%2B)%0A%20%20%20%20%20%20%20%20color%5Bi%5D%20%3D%20WHITE%3B%0A%20%0A%20%20%20%20%2F%2F%20Do%20a%20DFS%20traversal%20beginning%20with%20all%0A%20%20%20%20%2F%2F%20vertices%0A%20%20%20%20for%20(int%20i%20%3D%200%3B%20i%20%3C%20V%3B%20i%2B%2B)%0A%20%20%20%20%20%20%20%20if%20(color%5Bi%5D%20%3D%3D%20WHITE)%0A%20%20%20%20%20%20%20%20%20%20%20if%20(DFSUtil(i%2C%20color)%20%3D%3D%20true)%0A%20%20%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%0A%2F%2F%20Driver%20code%20to%20test%20above%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%20(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%0A%20%20%20%20return%200%3B%0A%7D%0A%0A\u201d message=\u201d\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n<p>Output :<\/p>\n<pre>Graph contains cycle<\/pre>\n<p>Time complexity of above solution is O(V + E) where V is number of vertices and E is number of edges in the graph.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Detect Cycle in a directed graph using colors-Graph cycle-Depth First Traversal can be used to detect cycle in a Graph. DFS for a connected graph.<\/p>\n","protected":false},"author":1,"featured_media":31270,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[81352],"tags":[76188,76186,76185,76184,81977,76183,76187,81978],"class_list":["post-27655","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-graph-cycle","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-directed-graph-python","tag-detect-cycle-in-undirected-graph","tag-detect-cycle-in-undirected-graph-in-c","tag-find-cycle-in-directed-graph"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/27655","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=27655"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/27655\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media\/31270"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=27655"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=27655"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=27655"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}