{"id":27541,"date":"2018-02-06T20:56:49","date_gmt":"2018-02-06T15:26:49","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=27541"},"modified":"2018-02-06T20:56:49","modified_gmt":"2018-02-06T15:26:49","slug":"union-find-algorithm-set-1-detect-cycle-undirected-graph-3","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/union-find-algorithm-set-1-detect-cycle-undirected-graph-3\/","title":{"rendered":"Union-Find Algorithm | Set 1 (Detect Cycle in an Undirected Graph)"},"content":{"rendered":"

A disjoint-set data structure<\/a><\/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

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

\"Union-Find<\/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
 
 <\/div> 
\/\/ A union-find algorithm to detect cycle in a graph#include <stdio.h>#include <stdlib.h>#include <string.h> \/\/ a structure to represent an edge in graphstruct Edge{    int src, dest;}; \/\/ a structure to represent a graphstruct Graph{    \/\/ V-> Number of vertices, E-> Number of edges    int V, E;     \/\/ graph is represented as an array of edges    struct Edge* edge;}; \/\/ Creates a graph with V vertices and E edgesstruct Graph* createGraph(int V, int E){    struct Graph* graph =            (struct Graph*) malloc( sizeof(struct Graph) );    graph->V = V;    graph->E = E;     graph->edge =         (struct Edge*) malloc( graph->E * sizeof( struct Edge ) );     return graph;} \/\/ A utility function to find the subset of an element iint 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 notint isCycle( struct Graph* graph ){    \/\/ Allocate memory for creating V subsets    int *parent = (int*) malloc( graph->V * sizeof(int) );     \/\/ Initialize all subsets as single element sets    memset(parent, -1, sizeof(int) * graph->V);     \/\/ 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 = find(parent, graph->edge[i].src);        int y = find(parent, graph->edge[i].dest);         if (x == y)            return 1;         Union(parent, x, y);    }    return 0;} \/\/ Driver program to test above functionsint main(){    \/* Let us create following graph         0        |  \\        |    \\        1-----2 *\/        int V = 3, E = 3;    struct Graph* graph = createGraph(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 (isCycle(graph))        printf( "graph contains cycle" );    else        printf( "graph doesn't contain cycle" );     return 0;}<\/code><\/pre> <\/div>\n
Output:<\/p>\n
graph contains cycle<\/pre>\n","protected":false},"excerpt":{"rendered":"
Union-Find Algorithm | Set 1 (Detect Cycle in an Undirected Graph)-Graph cycle-A disjoint-set data structure is a data structure that keeps track of a set.<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[81350,81352],"tags":[76546,76378,81747,76366,76368,76365,76367,76364],"class_list":["post-27541","post","type-post","status-publish","format-standard","hentry","category-graph","category-graph-cycle","tag-detect-cycle-in-directed-graph","tag-disjoint-set-data-structure-c","tag-disjoint-set-data-structure-example","tag-union-find-algorithm-c","tag-union-find-algorithm-java","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\/27541","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=27541"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/27541\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=27541"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=27541"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=27541"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}