In this blog, we will discuss the union-find algorithm. But before moving further we need to understand the meaning of a disjoint set. We can call two sets as disjoint if the intersection of two sets is an empty set. In other words, there is no common element between the two sets.
The union find is also known as set union. The disjoint-set data structure is a type of data structure that maintains a set of elements partitioned into a number of disjoint subsets. The union find algorithm is used to perform the following operations:
Find operation: This operation is used to determine which subset a particular element belongs to. It can also be used to determine whether two elements belong to the same set.
Union operation: The union operation is used to join two elements or subsets in a single subset. But before performing union operations we need to find whether two subsets belong to the same set.
Examples
Let us consider the following example:
Union(1, 2)
Since, 1 and 2 do not belong to the same subset already therefore we can perform the union operation to unite them. After union, both 1 and 2 belong to the same set:
Union(2, 3)
Since, 2 and 3 do not belong to the same subset already therefore we can perform the union operation to unite them. After union, both 2 and 3 belong to the same set:
As you can see above, now all the three elements: 1, 2 and 3 belong to the same set.
Determining cycle in a graph
You are given a graph and you need to determine whether the graph contains a cycle or not.
Input 1:
Output 1:
Cycle exist in the graph
Input 2:
Output 2: Cycle exist in the graph
Algorithm
Follow the below steps to implement the intuition:
Initially create a parent[] array and track all the subsets.
Now traverse to all the edges:
Check to which subset each of the nodes belong to by finding the parent[] array till the node and the parent are the same.
If there are two nodes that are already part of the same subset then there exists a cycle. Therefore, print “Cycle exists in the graph”
Otherwise, perform union operation on those two nodes or subsets.
If no cycle is found, print “Cycle doesn’t exist in the graph”.
The implementation of the approach is given below:
Example 1
Source Code:
#include <iostream> usingnamespacestd; // Edge class classEdge { public: int u, v; }; // A class to represent a graph classGraph { public: // "vertices" represents the total number of vertices // "edges" represents the total number of edges int vertices, edges; // Graph is represented as an array of edges Edge* edge; }; // Creates a graph with V vertices and E edges Graph* constructGraph(int vertices, int edges) { Graph* graph = new Graph(); graph-> vertices = vertices; graph->edges = edges; graph->edge = new Edge[graph-> edges * sizeof(Edge)]; return graph; } // A utility function to find the subset of an element i intfind(int parent[], int u) { if (parent[u] == u) return u; return find(parent, parent[u]); } // A utility function to do union of two subsets voidunionNodes(int parent[], int u, int v) { parent[u] = v; } intcheckCycle(Graph* graph) { // Allocate memory for creating V subsets int* parent = newint[graph-> vertices * sizeof(int)]; // Initialize with the self parent initially for(int index = 0; index < sizeof(int) * graph -> vertices; index++) { parent[index] = index; } // Iterate over the edges for (int index = 0; index < graph-> edges; ++index) { int parent1 = find(parent, graph->edge[index].u); int parent2 = find(parent, graph->edge[index].v); if (parent1 == parent2) return1; unionNodes(parent, parent1, parent2); } return0; } intmain() { int vertices = 4, edges = 4; // Construct the graph Graph* graph = constructGraph(vertices, edges); // add edge 0-1 graph->edge[0].u = 0; graph->edge[0].v = 1; // add edge 1-2 graph->edge[1].u = 1; graph->edge[1].v = 2; // add edge 2-3 graph->edge[2].u = 2; graph->edge[2].v = 3; // add edge 3-0 graph->edge[3].u = 3; graph->edge[3].v = 0; // add edge 3-4 graph->edge[4].u = 4; graph->edge[4].v = 0; if (checkCycle(graph)) cout << "Cycle exists in the graph"; else cout << "Cycle doesn't exist in the graph"; return0; }
Output:
Example 2
Source Code:
#include <iostream> usingnamespacestd; // Edge class classEdge { public: int u, v; }; // A class to represent a graph classGraph { public: // "vertices" represents the total number of vertices // "edges" represents the total number of edges int vertices, edges; // Graph is represented as an array of edges Edge* edge; }; // Creates a graph with V vertices and E edges Graph* constructGraph(int vertices, int edges) { Graph* graph = new Graph(); graph-> vertices = vertices; graph->edges = edges; graph->edge = new Edge[graph-> edges * sizeof(Edge)]; return graph; } // A utility function to find the subset of an element i intfind(int parent[], int u) { if (parent[u] == u) return u; return find(parent, parent[u]); } // A utility function to do union of two subsets voidunionNodes(int parent[], int u, int v) { parent[u] = v; } intcheckCycle(Graph* graph) { // Allocate memory for creating V subsets int* parent = newint[graph-> vertices * sizeof(int)]; // Initialize with the self parent initially for(int index = 0; index < sizeof(int) * graph -> vertices; index++) { parent[index] = index; } // Iterate over the edges for (int index = 0; index < graph-> edges; ++index) { int parent1 = find(parent, graph->edge[index].u); int parent2 = find(parent, graph->edge[index].v); if (parent1 == parent2) return1; unionNodes(parent, parent1, parent2); } return0; } intmain() { int vertices = 3, edges = 2; // Construct the graph Graph* graph = constructGraph(vertices, edges); // add edge 0-1 graph->edge[0].u = 0; graph->edge[0].v = 1; // add edge 1-2 graph->edge[1].u = 1; graph->edge[1].v = 2; if (checkCycle(graph)) cout << "Cycle exists in the graph"; else cout << "Cycle doesn't exist in the graph"; return0; }
Output:
As you can see in the output, there doesn’t exist any cycle in the graph.
In this blog, we discussed the union find algorithm. We also illustrated its implementation in C++. We believe that this blog has been interesting for you.
