{"id":25960,"date":"2017-10-25T22:03:23","date_gmt":"2017-10-25T16:33:23","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=25960"},"modified":"2017-10-25T22:03:23","modified_gmt":"2017-10-25T16:33:23","slug":"java-programming-union-find-algorithm-set-1-detect-cycle-undirected-graph","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/java-programming-union-find-algorithm-set-1-detect-cycle-undirected-graph\/","title":{"rendered":"Java 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
Java Programming:<\/strong><\/p>\n[pastacode lang=\u201djava\u201d manual=\u201d%2F%2F%20Java%20Program%20for%20union-find%20algorithm%20to%20detect%20cycle%20in%20a%20graph%0Aimport%20java.util.*%3B%0Aimport%20java.lang.*%3B%0Aimport%20java.io.*%3B%0A%20%0Aclass%20Graph%0A%7B%0A%20%20%20%20int%20V%2C%20E%3B%20%20%20%20%2F%2F%20V-%3E%20no.%20of%20vertices%20%26%20E-%3Eno.of%20edges%0A%20%20%20%20Edge%20edge%5B%5D%3B%20%2F%2F%20%2Fcollection%20of%20all%20edges%0A%20%0A%20%20%20%20class%20Edge%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20int%20src%2C%20dest%3B%0A%20%20%20%20%7D%3B%0A%20%0A%20%20%20%20%2F%2F%20Creates%20a%20graph%20with%20V%20vertices%20and%20E%20edges%0A%20%20%20%20Graph(int%20v%2Cint%20e)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20V%20%3D%20v%3B%0A%20%20%20%20%20%20%20%20E%20%3D%20e%3B%0A%20%20%20%20%20%20%20%20edge%20%3D%20new%20Edge%5BE%5D%3B%0A%20%20%20%20%20%20%20%20for%20(int%20i%3D0%3B%20i%3Ce%3B%20%2B%2Bi)%0A%20%20%20%20%20%20%20%20%20%20%20%20edge%5Bi%5D%20%3D%20new%20Edge()%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F%2F%20A%20utility%20function%20to%20find%20the%20subset%20of%20an%20element%20i%0A%20%20%20%20int%20find(int%20parent%5B%5D%2C%20int%20i)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20if%20(parent%5Bi%5D%20%3D%3D%20-1)%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20i%3B%0A%20%20%20%20%20%20%20%20return%20find(parent%2C%20parent%5Bi%5D)%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F%2F%20A%20utility%20function%20to%20do%20union%20of%20two%20subsets%0A%20%20%20%20void%20Union(int%20parent%5B%5D%2C%20int%20x%2C%20int%20y)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20int%20xset%20%3D%20find(parent%2C%20x)%3B%0A%20%20%20%20%20%20%20%20int%20yset%20%3D%20find(parent%2C%20y)%3B%0A%20%20%20%20%20%20%20%20parent%5Bxset%5D%20%3D%20yset%3B%0A%20%20%20%20%7D%0A%20%0A%20%0A%20%20%20%20%2F%2F%20The%20main%20function%20to%20check%20whether%20a%20given%20graph%0A%20%20%20%20%2F%2F%20contains%20cycle%20or%20not%0A%20%20%20%20int%20isCycle(%20Graph%20graph)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%2F%2F%20Allocate%20memory%20for%20creating%20V%20subsets%0A%20%20%20%20%20%20%20%20int%20parent%5B%5D%20%3D%20new%20int%5Bgraph.V%5D%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20Initialize%20all%20subsets%20as%20single%20element%20sets%0A%20%20%20%20%20%20%20%20for%20(int%20i%3D0%3B%20i%3Cgraph.V%3B%20%2B%2Bi)%0A%20%20%20%20%20%20%20%20%20%20%20%20parent%5Bi%5D%3D-1%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20Iterate%20through%20all%20edges%20of%20graph%2C%20find%20subset%20of%20both%0A%20%20%20%20%20%20%20%20%2F%2F%20vertices%20of%20every%20edge%2C%20if%20both%20subsets%20are%20same%2C%20then%0A%20%20%20%20%20%20%20%20%2F%2F%20there%20is%20cycle%20in%20graph.%0A%20%20%20%20%20%20%20%20for%20(int%20i%20%3D%200%3B%20i%20%3C%20graph.E%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%20int%20x%20%3D%20graph.find(parent%2C%20graph.edge%5Bi%5D.src)%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20int%20y%20%3D%20graph.find(parent%2C%20graph.edge%5Bi%5D.dest)%3B%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20(x%20%3D%3D%20y)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20return%201%3B%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20graph.Union(parent%2C%20x%2C%20y)%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%20return%200%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F%2F%20Driver%20Method%0A%20%20%20%20public%20static%20void%20main%20(String%5B%5D%20args)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%2F*%20Let%20us%20create%20following%20graph%0A%20%20%20%20%20%20%20%20%200%0A%20%20%20%20%20%20%20%20%7C%20%20%5C%0A%20%20%20%20%20%20%20%20%7C%20%20%20%20%5C%0A%20%20%20%20%20%20%20%201\u2014\u20132%20*%2F%0A%20%20%20%20%20%20%20%20int%20V%20%3D%203%2C%20E%20%3D%203%3B%0A%20%20%20%20%20%20%20%20Graph%20graph%20%3D%20new%20Graph(V%2C%20E)%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20add%20edge%200-1%0A%20%20%20%20%20%20%20%20graph.edge%5B0%5D.src%20%3D%200%3B%0A%20%20%20%20%20%20%20%20graph.edge%5B0%5D.dest%20%3D%201%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20add%20edge%201-2%0A%20%20%20%20%20%20%20%20graph.edge%5B1%5D.src%20%3D%201%3B%0A%20%20%20%20%20%20%20%20graph.edge%5B1%5D.dest%20%3D%202%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20add%20edge%200-2%0A%20%20%20%20%20%20%20%20graph.edge%5B2%5D.src%20%3D%200%3B%0A%20%20%20%20%20%20%20%20graph.edge%5B2%5D.dest%20%3D%202%3B%0A%20%0A%20%20%20%20%20%20%20%20if%20(graph.isCycle(graph)%3D%3D1)%0A%20%20%20%20%20%20%20%20%20%20%20%20System.out.println(%20%22graph%20contains%20cycle%22%20)%3B%0A%20%20%20%20%20%20%20%20else%0A%20%20%20%20%20%20%20%20%20%20%20%20System.out.println(%20%22graph%20doesn\u2019t%20contain%20cycle%22%20)%3B%0A%20%20%20%20%7D%0A%7D\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":"
Java 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,2139],"tags":[76366,76375,76365,76374,76367,76376,76377,76364],"class_list":["post-25960","post","type-post","status-publish","format-standard","hentry","category-coding","category-dfs-and-bfs","category-graph-algorithms","category-java","tag-union-find-algorithm-c","tag-union-find-complexity","tag-union-find-geeksforgeeks","tag-union-find-java","tag-union-find-path-compression","tag-union-find-princeton","tag-union-find-python","tag-union-find-wiki"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/25960","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=25960"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/25960\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=25960"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=25960"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=25960"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}