### Union-Find Algorithm in Graph

Welcome to our beginner's guide to the Union-Find Algorithm in Graph Theory! Union-Find is a fundamental algorithm used to efficiently manage disjoint sets, often applied in graph theory for tasks like determining connected components and detecting cycles. Let's explore this powerful algorithm together!

## Understanding the Problem Statement

Before diving into the Union-Find Algorithm, let's understand the problem it aims to solve. In many graph-related scenarios, we encounter the need to group elements into sets and perform operations like merging sets and finding whether two elements belong to the same set.

Consider a scenario where we have a graph with several nodes and edges connecting them. We want to efficiently answer questions like:

- Are two nodes connected?
- Which nodes are part of the same connected component?
- Is there a cycle in the graph?

The Union-Find Algorithm provides an elegant solution to address these questions by efficiently managing sets and their relationships.

## What is the Union-Find Algorithm?

The Union-Find Algorithm, also known as Disjoint-Set Union (DSU) or Merge-Find, is a data structure and algorithm used to maintain a collection of disjoint sets and efficiently perform operations like union and find.

The two main operations supported by the Union-Find data structure are:

**Union:**Merge two sets into one set.**Find:**Determine which set a particular element belongs to.

These operations allow us to efficiently manage sets and answer queries related to connectivity and cycles in graphs.

**How does Union-Find Work?**

The Union-Find data structure maintains a forest of trees, where each tree represents a disjoint set. Initially, each element is in its own singleton set, and each set is represented by a tree with a single node.

The Union-Find Algorithm supports two key operations:

**Union (Merge):**Merge two sets by connecting the roots of their respective trees.**Find (Find-Set):**Determine the root of the tree to which a particular element belongs.

These operations are performed efficiently to ensure that the overall complexity of the algorithm remains low.

## Example of the Union-Find Algorithm

### Example:1

The Union-Find Algorithm, also known as Disjoint Set Union (DSU), is a data structure that keeps track of a set of elements partitioned into multiple disjoint (non-overlapping) subsets. Let's demonstrate it using a simple graph of 6 nodes.

1 --- 2 5 | / | | / | 3 --- 4 6 7

In this scenario:

- Initially, each node is its own set.
- The operations involved are
*find*(determining the root of a set containing an element) and*union*(merging two sets).

**Union-Find Operations:**

- Starting state: Each node is in its own set.
- Perform
*Union(1, 2)*: Merges sets of 1 and 2. - Perform
*Union(3, 4)*: Merges sets of 3 and 4. - Perform
*Union(5, 6)*: Merges sets of 5 and 6. - Perform
*Union(6, 7)*: Merges sets of 6 and 7 (which also includes 5). - Perform
*Find(3)*: Returns the representative of the set containing 3, which is 3 itself. - Perform
*Find(7)*: Returns the representative of the set containing 7, which is 5.

1 2 3 4 5 6 7

1 --- 2 3 4 5 6 7

1 --- 2 3 --- 4 5 6 7

1 --- 2 3 --- 4 5 --- 6 7

1 --- 2 3 --- 4 5 --- 6 --- 7

### Example:2

We will demonstrate a more complex use of the Union-Find Algorithm using the following graph structure:

1 --- 2 5 \ / \ / \ \ / \ / \ 3 4 6 --- 7 \ / \ / \ / \ / 8

In this graph:

- Initially, each node is in its own set.
- We will perform a series of union operations to merge these sets.

**Union-Find Operations:**

- Starting state: Each node is in its own set.
- Perform
*Union(1, 2)*: Merges sets of 1 and 2. - Perform
*Union(2, 3)*: Merges sets of 2 (including 1) and 3. - Perform
*Union(2, 4)*: Merges sets of 2 (including 1, 3) and 4. - Perform
*Union(5, 6)*: Merges sets of 5 and 6. - Perform
*Union(6, 7)*: Merges sets of 6 (including 5) and 7. - Perform
*Union(3, 8)*: Merges sets of 3 (including 1, 2, 4) and 8. - Perform
*Find(4)*: Returns the representative of the set containing 4, which is 1. - Perform
*Find(7)*: Returns the representative of the set containing 7, which is 5.

1 2 3 4 5 6 7 8

1 --- 2 3 4 5 6 7 8

1 --- 2 --- 3 4 5 6 7 8

1 --- 2 --- 3 --- 4 5 6 7 8

1 --- 2 --- 3 --- 4 5 --- 6 7 8

1 --- 2 --- 3 --- 4 5 --- 6 --- 7 8

1 --- 2 --- 3 --- 4 --- 8 5 --- 6 --- 7

**Complexity:**

The time complexity for each Union or Find operation can be nearly O(1) on average when using path compression and union by rank optimizations.

This example illustrates how the Union-Find Algorithm efficiently merges different sets and finds the representative of each set.

**Example Application of Union-Find: Detecting Cycles in Graphs**

One common application of the Union-Find Algorithm is detecting cycles in undirected graphs. A cycle exists in a graph when there is a path from a vertex back to itself. By using the Union-Find Algorithm, we can efficiently determine whether adding an edge to the graph would create a cycle.

The algorithm works by performing the following steps:

- For each edge (u, v) in the graph:
- If the endpoints u and v belong to the same set, then adding the edge (u, v) would create a cycle.
- Otherwise, merge the sets containing u and v.

## Implementing Union-Find Algorithm in code

Now, let's take a look at how we can implement the Union-Find Algorithm in code. We'll provide examples in several programming languages to help you get started:

```
package codeKatha;
public class UnionFind {
private int[] parent;
private int[] rank;
public UnionFind(int n) {
parent = new int[n];
rank = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
rank[i] = 0;
}
}
public int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]);
}
return parent[x];
}
public void union(int x, int y) {
int rootX = find(x);
int rootY = find(y);
if (rootX != rootY) {
if (rank[rootX] < rank[rootY]) {
parent[rootX] = rootY;
} else if (rank[rootX] > rank[rootY]) {
parent[rootY] = rootX;
} else {
parent[rootY] = rootX;
rank[rootX]++;
}
}
}
}
```

```
#include <vector>
class UnionFind {
private:
std::vector<int> parent;
std::vector<int> rank;
public:
UnionFind(int n) {
parent.resize(n);
rank.resize(n);
for (int i = 0; i < n; i++) {
parent[i] = i;
rank[i] = 0;
}
}
int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]);
}
return parent[x];
}
void unionSets(int x, int y) {
int rootX = find(x);
int rootY = find(y);
if (rootX != rootY) {
if (rank[rootX] < rank[rootY]) {
parent[rootX] = rootY;
} else if (rank[rootX] > rank[rootY]) {
parent[rootY] = rootX;
} else {
parent[rootY] = rootX;
rank[rootX]++;
}
}
}
};
```

```
class UnionFind:
def __init__(self, n):
self.parent = [i for i in range(n)]
self.rank = [0] * n
def find(self, x):
if self.parent[x] != x:
self
.parent[x] = self.find(self.parent[x])
return self.parent[x]
def union(self, x, y):
rootX = self.find(x)
rootY = self.find(y)
if rootX != rootY:
if self.rank[rootX] < self.rank[rootY]:
self.parent[rootX] = rootY
elif self.rank[rootX] > self.rank[rootY]:
self.parent[rootY] = rootX
else:
self.parent[rootY] = rootX
self.rank[rootX] += 1
```

```
class UnionFind {
constructor(n) {
this.parent = new Array(n);
this.rank = new Array(n).fill(0);
for (let i = 0; i < n; i++) {
this.parent[i] = i;
}
}
find(x) {
if (this.parent[x] !== x) {
this.parent[x] = this.find(this.parent[x]);
}
return this.parent[x];
}
union(x, y) {
let rootX = this.find(x);
let rootY = this.find(y);
if (rootX !== rootY) {
if (this.rank[rootX] < this.rank[rootY]) {
this.parent[rootX] = rootY;
} else if (this.rank[rootX] > this.rank[rootY]) {
this.parent[rootY] = rootX;
} else {
this.parent[rootY] = rootX;
this.rank[rootX]++;
}
}
}
}
```

## Graph: Concept and Important Algorithms

1. Basics of Graph Data Structure2. Breadth-First Search (BFS) in Graph

3. Depth-First Search (DFS) in Graph

4. Topological Sort in Graph

5. Union-Find Algorithm in Graph

6. Prim's Algorithm in Graph

7. Dijkstra's Algorithm in Graph

8. Kruskal's Algorithm in Graph

Congratulations! You've now learned the basics of the Union-Find Algorithm in graph theory. Feel free to experiment with the provided code examples and explore further applications of Union-Find in your projects.

## Comments

## Post a Comment