{"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=”banner”]\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
 
 <\/div> 
\/\/ Java Program for union-find algorithm to detect cycle in a graphimport java.util.*;import java.lang.*;import java.io.*; class Graph{    int V, E;    \/\/ V-> no. of vertices & E->no.of edges    Edge edge[]; \/\/ \/collection of all edges     class Edge    {        int src, dest;    };     \/\/ Creates a graph with V vertices and E edges    Graph(int v,int e)    {        V = v;        E = e;        edge = new Edge[E];        for (int i=0; i<e; ++i)            edge[i] = new Edge();    }     \/\/ A utility function to find the subset of an element i    int find(int parent[], int i)    {        if (parent[i] == -1)            return i;        return find(parent, parent[i]);    }     \/\/ A utility function to do union of two subsets    void Union(int parent[], int x, int y)    {        int xset = find(parent, x);        int yset = find(parent, y);        parent[xset] = yset;    }      \/\/ The main function to check whether a given graph    \/\/ contains cycle or not    int isCycle( Graph graph)    {        \/\/ Allocate memory for creating V subsets        int parent[] = new int[graph.V];         \/\/ Initialize all subsets as single element sets        for (int i=0; i<graph.V; ++i)            parent[i]=-1;         \/\/ Iterate through all edges of graph, find subset of both        \/\/ vertices of every edge, if both subsets are same, then        \/\/ there is cycle in graph.        for (int i = 0; i < graph.E; ++i)        {            int x = graph.find(parent, graph.edge[i].src);            int y = graph.find(parent, graph.edge[i].dest);             if (x == y)                return 1;             graph.Union(parent, x, y);        }        return 0;    }     \/\/ Driver Method    public static void main (String[] args)    {        \/* Let us create following graph         0        |  \\        |    \\        1-----2 *\/        int V = 3, E = 3;        Graph graph = new Graph(V, E);         \/\/ add edge 0-1        graph.edge[0].src = 0;        graph.edge[0].dest = 1;         \/\/ add edge 1-2        graph.edge[1].src = 1;        graph.edge[1].dest = 2;         \/\/ add edge 0-2        graph.edge[2].src = 0;        graph.edge[2].dest = 2;         if (graph.isCycle(graph)==1)            System.out.println( "graph contains cycle" );        else            System.out.println( "graph doesn't contain cycle" );    }}<\/code><\/pre> <\/div>\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=”banner”]\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}]}}