{"id":25988,"date":"2017-10-26T09:25:55","date_gmt":"2017-10-26T03:55:55","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=25988"},"modified":"2018-10-30T15:38:29","modified_gmt":"2018-10-30T10:08:29","slug":"python-algorithm-detect-cycle-undirected-graph","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/python-algorithm-detect-cycle-undirected-graph\/","title":{"rendered":"Detect cycle in an undirected graph"},"content":{"rendered":"<h3 id=\"python-algorithm-detect-cycle-in-an-undirected-graph\"><span style=\"color: #003366;\"><strong>Python Algorithm: detect cycle in an undirected graph:<\/strong><\/span><\/h3>\n<p>Given an <a href=\"https:\/\/www.wikitechy.com\/technology\/detect-cycle-undirected-graph\/\" target=\"_blank\" rel=\"noopener\">undirected graph<\/a>, how to check if there is a cycle in the graph? For example, the following graph has a cycle 1-0-2-1.<\/p>\n<p>We have discussed cycle detection for directed graph. We have also discussed a <a href=\"https:\/\/www.wikitechy.com\/technology\/25974-2\/\" target=\"_blank\" rel=\"noopener\">union-find algorithm for cycle detection in undirected graphs<\/a>. The time complexity of the union-find algorithm is <strong>O(ELogV)<\/strong>. Like directed graphs, we can use DFS to detect cycle in an undirected graph in <strong>O(V+E)<\/strong> time. We do a <a href=\"https:\/\/www.wikitechy.com\/technology\/python-algorithm-depth-first-traversal-dfs-graph\/\" target=\"_blank\" rel=\"noopener\">DFS traversal<\/a> of the given graph. For every visited vertex \u2018<strong>v<\/strong>\u2019, if there is an adjacent \u2018<strong>u<\/strong>\u2019 such that u is already visited and u is not parent of v, then there is a cycle in graph. If we don\u2019t find such an adjacent for any vertex, we say that there is no cycle. The assumption of this approach is that there are no parallel edges between any two vertices.<\/p>\n<h3 id=\"python-programming-to-detect-cycle-in-an-undirected-graph\"><span style=\"color: #003366;\"><strong>Python Programming to detect cycle in an undirected graph:<\/strong><\/span><\/h3>\n[pastacode lang=\u201dpython\u201d manual=\u201d%23%20Python%20Program%20to%20detect%20cycle%20in%20an%20undirected%20graph%0A%20%0Afrom%20collections%20import%20defaultdict%0A%20%20%0A%23This%20class%20represents%20a%20undirected%20graph%20using%20adjacency%20list%20representation%0Aclass%20Graph%3A%0A%20%20%0A%20%20%20%20def%20__init__(self%2Cvertices)%3A%0A%20%20%20%20%20%20%20%20self.V%3D%20vertices%20%23No.%20of%20vertices%0A%20%20%20%20%20%20%20%20self.graph%20%3D%20defaultdict(list)%20%23%20default%20dictionary%20to%20store%20graph%0A%20%0A%20%20%0A%20%20%20%20%23%20function%20to%20add%20an%20edge%20to%20graph%0A%20%20%20%20def%20addEdge(self%2Cv%2Cw)%3A%0A%20%20%20%20%20%20%20%20self.graph%5Bv%5D.append(w)%20%23Add%20w%20to%20v_s%20list%0A%20%20%20%20%20%20%20%20self.graph%5Bw%5D.append(v)%20%23Add%20v%20to%20w_s%20list%0A%20%20%0A%20%20%20%20%23%20A%20recursive%20function%20that%20uses%20visited%5B%5D%20and%20parent%20to%20detect%0A%20%20%20%20%23%20cycle%20in%20subgraph%20reachable%20from%20vertex%20v.%0A%20%20%20%20def%20isCyclicUtil(self%2Cv%2Cvisited%2Cparent)%3A%0A%20%0A%20%20%20%20%20%20%20%20%23Mark%20the%20current%20node%20as%20visited%20%0A%20%20%20%20%20%20%20%20visited%5Bv%5D%3D%20True%0A%20%0A%20%20%20%20%20%20%20%20%23Recur%20for%20all%20the%20vertices%20adjacent%20to%20this%20vertex%0A%20%20%20%20%20%20%20%20for%20i%20in%20self.graph%5Bv%5D%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20If%20the%20node%20is%20not%20visited%20then%20recurse%20on%20it%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20%20visited%5Bi%5D%3D%3DFalse%20%3A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20if(self.isCyclicUtil(i%2Cvisited%2Cv))%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20return%20True%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20If%20an%20adjacent%20vertex%20is%20visited%20and%20not%20parent%20of%20current%20vertex%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20then%20there%20is%20a%20cycle%0A%20%20%20%20%20%20%20%20%20%20%20%20elif%20%20parent!%3Di%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20return%20True%0A%20%20%20%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20return%20False%0A%20%20%20%20%20%20%20%20%20%0A%20%20%0A%20%20%20%20%23Returns%20true%20if%20the%20graph%20contains%20a%20cycle%2C%20else%20false.%0A%20%20%20%20def%20isCyclic(self)%3A%0A%20%20%20%20%20%20%20%20%23%20Mark%20all%20the%20vertices%20as%20not%20visited%0A%20%20%20%20%20%20%20%20visited%20%3D%5BFalse%5D*(self.V)%0A%20%20%20%20%20%20%20%20%23%20Call%20the%20recursive%20helper%20function%20to%20detect%20cycle%20in%20different%0A%20%20%20%20%20%20%20%20%23DFS%20trees%0A%20%20%20%20%20%20%20%20for%20i%20in%20range(self.V)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20visited%5Bi%5D%20%3D%3DFalse%3A%20%23Don\u2019t%20recur%20for%20u%20if%20it%20is%20already%20visited%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20if(self.isCyclicUtil(i%2Cvisited%2C-1))%3D%3D%20True%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20return%20True%0A%20%20%20%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20return%20False%0A%20%0A%23%20Create%20a%20graph%20given%20in%20the%20above%20diagram%0Ag%20%3D%20Graph(5)%0Ag.addEdge(1%2C%200)%0Ag.addEdge(0%2C%202)%0Ag.addEdge(2%2C%200)%0Ag.addEdge(0%2C%203)%0Ag.addEdge(3%2C%204)%0A%20%0Aif%20g.isCyclic()%3A%0A%20%20%20%20print%20%22Graph%20contains%20cycle%22%0Aelse%20%3A%0A%20%20%20%20print%20%22Graph%20does%20not%20contain%20cycle%20%22%0Ag1%20%3D%20Graph(3)%0Ag1.addEdge(0%2C1)%0Ag1.addEdge(1%2C2)%0A%20%0A%20%0Aif%20g1.isCyclic()%3A%0A%20%20%20%20print%20%22Graph%20contains%20cycle%22%0Aelse%20%3A%0A%20%20%20%20print%20%22Graph%20does%20not%20contain%20cycle%20%22%0A%20%20%0A%23This%20code%20is%20contributed%20by%20Neelam%20Yadav\u201d message=\u201d\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n<h3 id=\"output\"><span style=\"color: #008000;\"><strong>Output:<\/strong><\/span><\/h3>\n<pre>Graph contains cycle\r\nGraph doesn't contain cycle<\/pre>\n<p><span style=\"color: #3366ff;\"><strong>Time Complexity:<\/strong> <\/span>The program does a simple DFS Traversal of graph and <a href=\"https:\/\/www.wikitechy.com\/technology\/python-programming-check-graph-strongly-connected-set-1-kosaraju-using-dfs\/\" target=\"_blank\" rel=\"noopener\">graph<\/a> is represented using adjacency list. So the time complexity is <strong>O(V+E)<\/strong><\/p>\n[ad type=\u201dbanner\u201d]\n","protected":false},"excerpt":{"rendered":"<p>Python Algorithm &#8211; Detect cycle in an undirected graph &#8211; Graph Algorithms &#8211; Given an undirected graph, how to check if there is a cycle in the graph<\/p>\n","protected":false},"author":1,"featured_media":31290,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1,74168,73906,4148],"tags":[76523,76185,76184,76187,76525,76190,76522,76524],"class_list":["post-25988","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-coding","category-dfs-and-bfs","category-graph-algorithms","category-python","tag-cycle-in-directed-graph","tag-detect-cycle-in-directed-graph-in-c","tag-detect-cycle-in-directed-graph-java","tag-detect-cycle-in-undirected-graph-in-c","tag-detect-cycle-in-undirected-graph-java","tag-find-all-cycles-in-a-directed-graph","tag-find-all-cycles-in-an-undirected-graph","tag-find-cycle-in-undirected-graph"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/25988","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=25988"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/25988\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media\/31290"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=25988"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=25988"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=25988"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}