# Union Find

Updated: 01 February 2024

Used to work with the problem of connecting objects and determining if those two objects are connected

Refers to the problem when given a set of objects N to be able to:

• Union - Connect two objects
• Connected - Check if a path that connects two objects exists

e.g. Given some set of items that are connected in a network

0---1   2   3---4
|
|
5   6---7   8---9

In the above example we have some items that are connected. In the above set we can ask a question like “Is 3 connected to 9”

# Implementation

In the implementation of the Union Find we will use a UnionFind data type that has union and connected methods

algorithms/union-find/interface.ts
export interface UnionFind {
connected(a: number, b: number): boolean;
union(a: number, b: number): void;
}


## Quick Find

An implementation can be seen below:

algorithms/union-find/quick-find.ts
import type { UnionFind } from "./interface";

export class QuickFind implements UnionFind {
/*
* Track the group associated with each item based on its index
*/
groups: number[];

/* Initially each item is identified by a group
* that is the same as its own index
*/
constructor(size: number) {
this.groups = new Array(size).fill(0).map((_, i) => i);
}

/*
* If two items are connected their groups will be the same
*/
connected(a: number, b: number) {
const groupA = this.groups[a];
const groupB = this.groups[b];

return groupA === groupB;
}

/*
* Joins two items by setting all items of the one group
* to the same as the other group
*/
union(a: number, b: number) {
const groupA = this.groups[a];
const groupB = this.groups[b];

/*
* Iterate through each item and if they are the same as B
* then update them to be A
*/
for (let index = 0; index < this.groups.length; index++) {
const group = this.groups[index];
if (group === groupB) {
this.groups[index] = groupA;
}
}
}
}


## Quick Union

Quick union is an implementation of union find that uses a tree to represent the data structure. In this implementation instead of storing the representative group we store the connections as a forest where each connected set is a tree

algorithms/union-find/quick-union.ts
export class QuickUnion {
/*
* Track the parent associated with each items.
* The element is a root node if the parent is the same as the node
*/
parents: number[];

/* Initially each item is identified by a parent
* that is the same as its own index
*/
constructor(size: number) {
this.parents = new Array(size).fill(0).map((_, i) => i);
}

/*
* Get the root of a given node
*/
root(a: number) {
let parent = a;
while (parent !== this.parents[a]) {
parent = this.parents[parent];
}

return parent;
}

/*
* If two items have the same root they are connected
*/
connected(a: number, b: number) {
return this.root(a) === this.root(b);
}

/*
* Joins a node by setting its root to that of the other node
*/
union(a: number, b: number) {
const root = this.root(a);
this.parents[b] = root;
}
}


## Weighted Quick Union

What slows down the quick union is traversing up through a long tree. THe idea here is to avoid tall trees, to do this we need to:

1. Keep track of size of each tree (number of objects)
2. Balance by linking root of smaller tree to root of larger tree
algorithms/union-find/weighted-quick-union.ts
import type { UnionFind } from "./interface";

export class WeightedQuickUnion implements UnionFind {
/*
* Track the parent associated with each items.
* The element is a root node if the parent is the same as the node
*/
parents: number[];

/*
* The number of elements in each tree
*/
sizes: number[];

/* Initially each item is identified by a parent
* that is the same as its own index
*/
constructor(size: number) {
this.parents = new Array(size).fill(0).map((_, i) => i);

this.sizes = new Array(size).fill(1);
}

/*
* Get the root of a given node
*/
root(a: number) {
let parent = a;
while (parent !== this.parents[a]) {
parent = this.parents[parent];
}

return parent;
}

/*
* If two items have the same root they are connected
*/
connected(a: number, b: number) {
return this.root(a) === this.root(b);
}

/*
* Joins a node by setting its root to that of the other node
*
* Differs from Quick Union by checking tree sizes and prefering a
* smaller tree where possible
*/
union(a: number, b: number) {
const rootA = this.root(a);
const rootB = this.root(b);

if (rootA === rootB) {
return;
}

const sizeA = this.sizes[rootA];
const sizeJ = this.sizes[rootB];
if (sizeA < sizeJ) {
this.parents[rootA] = rootB;
this.sizes[rootB] += sizeA;
} else {
this.parents[rootB] = rootA;
this.sizes[rootA] += sizeJ;
}
}
}


For this algorithm the depth of any node should be at most lg N (lg is shorthand for Log with base 2)

## Weighted Quick Union with Path Compression

By modifying the implementation to update the root of any item we read as we read it we can save a lot of read iterations in the future by updating each non-root node to move it a level up when we read it:

algorithms/union-find/weighted-quick-union-path-comp.ts
import type { UnionFind } from "./interface";

export class WeightedQuickUnionPathCompression implements UnionFind {
/*
* Track the parent associated with each items.
* The element is a root node if the parent is the same as the node
*/
parents: number[];

/*
* The number of elements in each tree
*/
sizes: number[];

/* Initially each item is identified by a parent
* that is the same as its own index
*/
constructor(size: number) {
this.parents = new Array(size).fill(0).map((_, i) => i);

this.sizes = new Array(size).fill(1);
}

/*
* Get the root of a given node
*/
root(a: number) {
let parent = a;
while (parent !== this.parents[parent]) {
// since we're already at this node we can just move it up a level
parent = this.parents[this.parents[parent]];
this.parents[parent] = parent;
}

return parent;
}

/*
* If two items have the same root they are connected
*/
connected(a: number, b: number) {
return this.root(a) === this.root(b);
}

/*
* Joins a node by setting its root to that of the other node
*
* Differs from Quick Union by checking tree sizes and prefering a
* smaller tree where possible
*/
union(a: number, b: number) {
const rootA = this.root(a);
const rootB = this.root(b);

if (rootA === rootB) {
return;
}

const sizeA = this.sizes[rootA];
const sizeB = this.sizes[rootB];
if (sizeA < sizeB) {
this.parents[rootA] = rootB;
this.sizes[rootB] += sizeA;
} else {
this.parents[rootB] = rootA;
this.sizes[rootA] += sizeB;
}
}
}


Since we have flattened the tree at every pass the union time of this agorithm makes it less than N + M lg* N (lg* is a super small value)

# Complexity

algorithminitunionfind
quick-findNN1
quick-unionNN (note)N
weighted-quick-unionNlg N (note)lg N
weighted-quick-union-pcNlg* Nlg N

(note) Includes cost of finding the root