Set 1 (Detect Cycle in a an Undirected Graph)
A
disjoint-set data structure is a data structure that keeps track of a set of elements partitioned into a number of disjoint (non-overlapping) subsets. A
union-find algorithm is an algorithm that performs two useful operations on such a data structure:
disjoint-set data structure可将数据分为不相交的子集的数据结构。
union-find algorithm在这种数据结构上执行两种有用的操作：
Find: Determine which subset a particular element is in. This can be used for determining if two elements are in the same subset.
Find:确定指定元素属于哪个子集。可以用于确定两个元素是否位于同一子集。
Union: Join two subsets into a single subset.
Union：将两个子集合并成一个。
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.
这里，我们讨论Disjoint Set Data Structure的一种应用：检查给定的图是否包含环。
Union-Find Algorithm can be used to check whether an undirected graph contains cycle or not. Note that we have discussed an
algorithm to detect cycle. This is another method based on Union-Find. This method assumes that graph doesn’t contain any self-loops.
We can keeps track of the subsets in a 1D array, lets call it parent[].
Let us consider the following graph:
0 | | 1-----2For each edge, make subsets using both the vertices of the edge. If both the vertices are in the same subset, a cycle is found.
Initially, all slots of parent array are initialized to -1 (means there is only one item in every subset).
0 1 2-1 -1 -1 Now process all edges one by one.
Edge 0-1: 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.
0 1 2 <----- 1 is made parent of 0 (1 is now representative of subset {0, 1})1 -1 -1Edge 1-2: 1 is in subset 1 and 2 is in subset 2. So, take union.
0 1 2 <----- 2 is made parent of 1 (2 is now representative of subset {0, 1, 2})1 2 -1Edge 0-2: 0 is in subset 2 and 2 is also in subset 2. Hence, including this edge forms a cycle.
How subset of 0 is same as 2?
0->1->2 // 1 is parent of 0 and 2 is parent of 1
Based on the above explanation, below is the code:
// 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 graph
struct Edge
{
int src, dest;
};
// a structure to represent a graph
struct 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 edges
struct 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 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( 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 functions
int main()
{
/* Let us create following graph
0
| \
| \
1-----2 */
struct Graph* graph = createGraph(3, 3);
// 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;
}
Output:
Graph contains cycleNote that the implementation of union() and find() is naive and takes O(n) time in worst case. These methods can be improved to O(Logn) using Union by Rank or Height. We will soon be discussing Union by Rank in a separate post.
This article is compiled by
Aashish Barnwal and reviewed by GeeksforGeeks team. Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.
Set 2 (Union By Rank and Path Compression)
In the
previous post, we introduced union find algorithm and used it to detect cycle in a graph. We used followingunion() and find() operations for subsets.
// Naive implementation of findint find(int parent[], int i){ if (parent[i] == -1) return i; return find(parent, parent[i]);} // Naive implementation of union()void Union(int parent[], int x, int y){ int xset = find(parent, x); int yset = find(parent, y); parent[xset] = yset;}The above union() and find() are naive and the worst case time complexity is linear. The trees created to represent subsets can be skewed and can become like a linked list. Following is an example worst case scenario.
Let there be 4 elements 0, 1, 2, 3Initially all elements are single element subsets.0 1 2 3 Do Union(0, 1) 1 2 3 / 0Do Union(1, 2) 2 3 / 1 /0Do Union(2, 3) 3 / 2 / 1 /0The above operations can be optimized to O(Log n) in worst case. The idea is to always attach smaller depth tree under the root of the deeper tree. This technique is called union by rank. The term rank is preferred instead of height because if path compression technique (we have discussed it below) is used, then rank is not always equal to height. Also, size (in place of height) of trees can also be used as rank. Using size as rank also yields worst case time complexity as O(Logn) (See
this for prrof)
Let us see the above example with union by rankInitially all elements are single element subsets.0 1 2 3 Do Union(0, 1) 1 2 3 / 0Do Union(1, 2) 1 3 / 0 2Do Union(2, 3) 1 / | 0 2 3The second optimization to naive method is Path Compression. The idea is to flatten the tree when find() is called. When find() is called for an element x, root of the tree is returned. The find() operation traverses up from x to find root. The idea of path compression is to make the found root as parent of x so that we don’t have to traverse all intermediate nodes again. If x is root of a subtree, then path (to root) from all nodes under x also compresses.
Let the subset {0, 1, .. 9} be represented as below and find() is calledfor element 3. 9 / | \ 4 5 6 / \ / 0 3 7 8 / 1 2 When find() is called for 3, we traverse up and find 9 as representativeof this subset. With path compression, we also make 3 as child of 9 so that when find() is called next time for 1, 2 or 3, the path to root is reduced. 9 / / \ 4 5 6 3 / / \ / 0 7 8 1 2 The two techniques complement each other. The time complexity of each operations becomes even smaller than O(Logn). In fact, amortized time complexity effectively becomes small constant.
Following is union by rank and path compression based implementation to find cycle in a graph.
// A union by rank and path compression based program to detect cycle in a graph#include <stdio.h>#include <stdlib.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;};struct subset{ int parent; int rank;};// 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 set of an element i// (uses path compression technique)int find(struct subset subsets[], int i){ // find root and make root as parent of i (path compression) if (subsets[i].parent != i) subsets[i].parent = find(subsets, subsets[i].parent); return subsets[i].parent;}// A function that does union of two sets of x and y// (uses union by rank)void Union(struct subset subsets[], int x, int y){ int xroot = find(subsets, x); int yroot = find(subsets, y); // Attach smaller rank tree under root of high rank tree // (Union by Rank) if (subsets[xroot].rank < subsets[yroot].rank) subsets[xroot].parent = yroot; else if (subsets[xroot].rank > subsets[yroot].rank) subsets[yroot].parent = xroot; // If ranks are same, then make one as root and increment // its rank by one else { subsets[yroot].parent = xroot; subsets[xroot].rank++; }}// The main function to check whether a given graph contains cycle or notint isCycle( struct Graph* graph ){ int V = graph->V; int E = graph->E; // Allocate memory for creating V sets struct subset *subsets = (struct subset*) malloc( V * sizeof(struct subset) ); for (int v = 0; v < V; ++v) { subsets[v].parent = v; subsets[v].rank = 0; } // Iterate through all edges of graph, find sets of both // vertices of every edge, if sets are same, then there is // cycle in graph. for(int e = 0; e < E; ++e) { int x = find(subsets, graph->edge[e].src); int y = find(subsets, graph->edge[e].dest); if (x == y) return 1; Union(subsets, 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;}Output:
Graph contains cycleWe will soon be discussing
Kruskal’s Algorithm as next application of Union-Find Algorithm.
References:
http://en.wikipedia.org/wiki/Disjoint-set_data_structureIITD Video LecturePlease write comments if you find anything incorrect, or you want to share more information about the topic discussed above.
