{"id":25974,"date":"2017-10-25T22:01:35","date_gmt":"2017-10-25T16:31:35","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=25974"},"modified":"2017-10-25T22:01:35","modified_gmt":"2017-10-25T16:31:35","slug":"25974-2","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/25974-2\/","title":{"rendered":"Python Programming – Union-Find Algorithm | Set 1 (Detect Cycle in an Undirected Graph)"},"content":{"rendered":"

A disjoint-set data structure<\/em> is a data structure that keeps track of a set of elements partitioned into a number of disjoint (non-overlapping) subsets.<\/span> A union-find algorithm<\/em><\/a> is an algorithm that performs two useful operations on such a data structure:<\/p>\n

Find:<\/strong><\/em> Determine which subset a particular element is in. This can be used for determining if two elements are in the same subset.<\/p>\n

Union:<\/strong><\/em> Join two subsets into a single subset.<\/p>\n

In this post, we will discuss an application of Disjoint Set Data Structure. The application is to check whether a given graph contains a cycle or not.<\/p>\n

Union-Find Algorithm<\/em> can be used to check whether an undirected graph contains cycle or not. Note that we have discussed an algorithm to detect cycle<\/a>. This is another method based on Union-Find<\/em>. This method assumes that graph doesn\u2019t contain any self-loops.
\nWe can keeps track of the subsets in a 1D array, lets call it parent[].<\/p>\n[ad type=\u201dbanner\u201d]\n

Let us consider the following graph:<\/p>\n

For each edge, make subsets using both the vertices of the edge. If both the vertices are in the same subset, a cycle is found.<\/p>\n

Initially, all slots of parent array are initialized to -1 (means there is only one item in every subset).<\/p>\n

0   1   2\r\n-1 -1  -1<\/pre>\n
Now process all edges one by one.<\/p>\n
Edge 0-1:<\/em> Find the subsets in which vertices 0 and 1 are. Since they are in different subsets, we take the union of them. For taking the union, either make node 0 as parent of node 1 or vice-versa.<\/p>\n
0   1   2    <----- 1 is made parent of 0 (1 is now representative of subset {0, 1})\r\n1  -1  -1<\/pre>\n
Edge 1-2:<\/em> 1 is in subset 1 and 2 is in subset 2. So, take union.<\/p>\n
0   1   2    <----- 2 is made parent of 1 (2 is now representative of subset {0, 1, 2})\r\n1   2  -1<\/pre>\n
Edge 0-2:<\/em> 0 is in subset 2 and 2 is also in subset 2. Hence, including this edge forms a cycle.<\/p>\n
How subset of 0 is same as 2?
\n0->1->2 \/\/ 1 is parent of 0 and 2 is parent of 1<\/p>\n
Based on the above explanation, below are implementations:<\/p>\n
Python Programming:<\/strong><\/p>\n[pastacode lang=\u201dpython\u201d manual=\u201d%23%20Python%20Program%20for%20union-find%20algorithm%20to%20detect%20cycle%20in%20a%20undirected%20graph%0A%23%20we%20have%20one%20egde%20for%20any%20two%20vertex%20i.e%201-2%20is%20either%201-2%20or%202-1%20but%20not%20both%0A%20%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%20%0A%20%0A%20%20%20%20%23%20function%20to%20add%20an%20edge%20to%20graph%0A%20%20%20%20def%20addEdge(self%2Cu%2Cv)%3A%0A%20%20%20%20%20%20%20%20self.graph%5Bu%5D.append(v)%0A%20%20%0A%20%20%20%20%23%20A%20utility%20function%20to%20find%20the%20subset%20of%20an%20element%20i%0A%20%20%20%20def%20find_parent(self%2C%20parent%2Ci)%3A%0A%20%20%20%20%20%20%20%20if%20parent%5Bi%5D%20%3D%3D%20-1%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20i%0A%20%20%20%20%20%20%20%20if%20parent%5Bi%5D!%3D%20-1%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20return%20self.find_parent(parent%2Cparent%5Bi%5D)%0A%20%0A%20%20%20%20%23%20A%20utility%20function%20to%20do%20union%20of%20two%20subsets%0A%20%20%20%20def%20union(self%2Cparent%2Cx%2Cy)%3A%0A%20%20%20%20%20%20%20%20x_set%20%3D%20self.find_parent(parent%2C%20x)%0A%20%20%20%20%20%20%20%20y_set%20%3D%20self.find_parent(parent%2C%20y)%0A%20%20%20%20%20%20%20%20parent%5Bx_set%5D%20%3D%20y_set%0A%20%0A%20%20%0A%20%20%0A%20%20%20%20%23%20The%20main%20function%20to%20check%20whether%20a%20given%20graph%0A%20%20%20%20%23%20contains%20cycle%20or%20not%0A%20%20%20%20def%20isCyclic(self)%3A%0A%20%20%20%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20%23%20Allocate%20memory%20for%20creating%20V%20subsets%20and%0A%20%20%20%20%20%20%20%20%23%20Initialize%20all%20subsets%20as%20single%20element%20sets%0A%20%20%20%20%20%20%20%20parent%20%3D%20%5B-1%5D*(self.V)%0A%20%0A%20%20%20%20%20%20%20%20%23%20Iterate%20through%20all%20edges%20of%20graph%2C%20find%20subset%20of%20both%0A%20%20%20%20%20%20%20%20%23%20vertices%20of%20every%20edge%2C%20if%20both%20subsets%20are%20same%2C%20then%0A%20%20%20%20%20%20%20%20%23%20there%20is%20cycle%20in%20graph.%0A%20%20%20%20%20%20%20%20for%20i%20in%20self.graph%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20for%20j%20in%20self.graph%5Bi%5D%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20x%20%3D%20self.find_parent(parent%2C%20i)%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20y%20%3D%20self.find_parent(parent%2C%20j)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20if%20x%20%3D%3D%20y%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%20%20%20%20self.union(parent%2Cx%2Cy)%0A%20%0A%20%0A%23%20Create%20a%20graph%20given%20in%20the%20above%20diagram%0Ag%20%3D%20Graph(3)%0Ag.addEdge(0%2C%201)%0Ag.addEdge(1%2C%202)%0Ag.addEdge(2%2C%200)%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%0A%20%20%0A%23This%20code%20is%20contributed%20by%20Neelam%20Yadav\u201d message=\u201d\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n
Output:<\/strong><\/p>\n
graph contains cycle<\/pre>\n
Note that the implementation of union()<\/em> and find()<\/em> is naive and takes O(n) time in worst case. These methods can be improved to O(Logn) using Union by Rank or Height<\/em>. We will soon be discussing Union by Rank<\/em> in a separate post.<\/p>\n[ad type=\u201dbanner\u201d]\n","protected":false},"excerpt":{"rendered":"
Python Programming – Union-Find Algorithm | Set 1 (Detect Cycle in an Undirected Graph) – Graph Algorithms – A disjoint-set data structure is a data.<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1,74168,73906,4148],"tags":[76361,76363,76366,76368,76362,76365,76367,76364],"class_list":["post-25974","post","type-post","status-publish","format-standard","hentry","category-coding","category-dfs-and-bfs","category-graph-algorithms","category-python","tag-disjoint-set-data-structure-python","tag-python-union-find-library","tag-union-find-algorithm-c","tag-union-find-algorithm-java","tag-union-find-algorithm-python","tag-union-find-geeksforgeeks","tag-union-find-path-compression","tag-union-find-wiki"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/25974","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=25974"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/25974\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=25974"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=25974"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=25974"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}