# Disjoint-Set/Union-Find Data Structure

May 01, 2020

## Quick Note

📝

Note: This post is part of the Data Structures and Algorithm series. To see more posts from this series, click here. The illustrations below are inspired by the Algorithms, Part I course on Coursera. All code examples from this series can be found here.

A ** disjoint-set** (also referred to as a

*union-find*data structure) is a data structure that tracks a set of elements partitioned into a group of disjoint subsets (also known as

*connected components*). Given this type of data structure, there are multiple algorithms that can be used to solve the two major equations for a disjoint-set, the

**command and the**

*Union***query, which we'll go into more detail below.**

*Find***Dynamic Connectivity**

- A dynamic connectivity structure maintains information about the connected components of a graph.
- Given a set of
*N*objects:- Connect two objects (the
command)*Union* - Determine if there is a path connecting the two objects (the
query)*Find*

- Connect two objects (the

### Union-Find Illustration

**Quick Find**

- Quick Find is an
*Eager*algorithm also used to solve the*dynamic connectivity*problem. - The
query for this algorithm is very efficient and is measured in constant time.*Find*- Given id[] of size
*N*, check if*p*and*q*are connected.

- Given id[] of size
- The
command is measured in quadratic time because the time to resolve is dependent on the size of the array and the number of values that must change as a result.*Union*- When changing a value of
`id[q]`

, you must also change all entries whose value is equal (connected) to`id[q]`

as well.

- When changing a value of

### Quick Find Illustration

### Quick Find Implementation

```
import DisjointSet from "./DisjointSet";
class QuickFind implements DisjointSet {
disjointSet: number[];
constructor(quantity: number) {
this.disjointSet = [];
for (let i = 0; i < quantity; i++) this.disjointSet[i] = i;
}
connected = (p: number, q: number): boolean => {
return this.disjointSet[p] === q;
};
union = (p: number, q: number): void => {
const pid = this.disjointSet[p];
const qid = this.disjointSet[q];
this.disjointSet.forEach((value, index) => {
if (value === pid) {
this.disjointSet[index] = qid;
}
});
};
}
export default QuickFind;
```

**Quick Union**

- Quick Union is a
*Lazy*algorithm that, again, is used to solve the*dynamic connectivity*problem. - Data structures implementing this algorithm are represented as trees in order to find the connected root of each element.
- The
query requires a traversal up the tree:*Find*- Given id[] of size
*N*, check if*p*and*q*have the same*root*.

- Given id[] of size
- The
command requires the*Union**find*query in order to determine each element's root before merging.- This command is measured in linear time because in order to merge the
*connected components*containing*p*and*q*, we must set the id of*p*'s root to the id of*q*'s root.

- This command is measured in linear time because in order to merge the

### Quick Union Illustration

### Quick Union Implementation

```
import DisjointSet from "./DisjointSet";
class QuickUnion implements DisjointSet {
disjointSet: number[];
constructor(quantity: number) {
this.disjointSet = [];
for (let i = 0; i < quantity; i++) this.disjointSet[i] = i;
}
private root(valueToCheck: number): number {
while (this.disjointSet[valueToCheck] !== valueToCheck) {
valueToCheck = this.disjointSet[valueToCheck];
}
return valueToCheck;
}
private isDirectChild(p: number, q: number): boolean {
return this.disjointSet[p] === q;
}
connected(p: number, q: number): boolean {
if (this.isDirectChild(p, q)) return true;
return this.root(p) === this.root(q);
}
union(p: number, q: number): void {
const rootP = this.root(p);
const rootQ = this.root(q);
this.disjointSet[rootP] = rootQ;
}
}
export default QuickUnion;
```

## Improvements to Quick Union

## Weighted Quick Union

- We can improve Quick Union by
*"weighting"*our algorithm. What this means is that anytime aoperation is performed, we will always link the root of the smaller tree to the root of the larger tree.*Union*- This helps to keep the overall tree structure relatively flat, compared to a normal quick-union tree (as pictured below), and ensures each node is never too far from the overall root node.
- The
query takes the time proportional to the depth of*Find**p*and*q*.- Because we are always setting the root of the smaller tree to that of the larger tree, the depth of any node is
*at most**log N*(where N is the number of nodes in the overall tree).

- Because we are always setting the root of the smaller tree to that of the larger tree, the depth of any node is

### Weighted Quick Union Illustration

### Weighted Quick Union Implementation

For the weighted quick union implementation, you can see below that our ** Find** query remains the same. For the

**operation, however, we are incrementing the size of the larger root by the size of the smaller root.**

*Union*```
import DisjointSet from "./DisjointSet";
class WeightedQuickUnion implements DisjointSet {
disjointSet: number[];
size: number[];
constructor(quantity: number) {
this.disjointSet = [];
this.size = [];
for (let i = 0; i < quantity; i++) {
this.disjointSet[i] = i;
this.size[i] = 1;
}
}
private root(valueToCheck: number): number {
while (this.disjointSet[valueToCheck] !== valueToCheck) {
valueToCheck = this.disjointSet[valueToCheck];
}
return valueToCheck;
}
private isDirectChild(p: number, q: number): boolean {
return this.disjointSet[p] === this.disjointSet[q];
}
connected(p: number, q: number): boolean {
if (this.isDirectChild(p, q)) return true;
return this.root(p) === this.root(q);
}
union(p: number, q: number): void {
const rootP = this.root(p);
const rootQ = this.root(q);
if (rootP === rootQ) return;
if (this.size[rootP] <= this.size[rootQ]) {
this.disjointSet[rootP] = rootQ;
this.size[rootQ] += this.size[rootP];
} else {
this.disjointSet[rootQ] = rootP;
this.size[rootP] += this.size[rootQ];
}
}
}
export default WeightedQuickUnion;
```

## Weighted Quick Union with Path Compression

- This algorithm can be improved even further by compressing the path to the overall root.
- So, after computing the root of
*p*, for any node that was passed over (6, 3, 1 in the following illustration), we'll set it to point to the new root as well. - This causes our overall tree to flatten even further, decreasing the time complexity to
*almost*linear.

- So, after computing the root of

### Weighted Quick Union with Path Compression Illustration

### Weighted QU with Path Compression Implementation

For this implementation, we're going to update our `root`

method so that for each traversal to an object's root, we'll set the value of every other node in the path to point to its grandparent, thereby halving the length to the object's root.

```
private root(valueToCheck: number): number {
while (this.disjointSet[valueToCheck] !== valueToCheck) {
this.disjointSet[valueToCheck] = this.disjointSet[
this.disjointSet[valueToCheck]
];
valueToCheck = this.disjointSet[valueToCheck];
}
return valueToCheck;
}
```