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
10---1 2 3---42 |3 |45 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
1export interface UnionFind {2 connected(a: number, b: number): boolean;3 union(a: number, b: number): void;4}
Quick Find
An implementation can be seen below:
1import type { UnionFind } from "./interface";2
3export class QuickFind implements UnionFind {4 /*5 * Track the group associated with each item based on its index6 */7 groups: number[];8
9 /* Initially each item is identified by a group10 * that is the same as its own index11 */12 constructor(size: number) {13 this.groups = new Array(size).fill(0).map((_, i) => i);14 }15
16 /*17 * If two items are connected their groups will be the same18 */19 connected(a: number, b: number) {20 const groupA = this.groups[a];21 const groupB = this.groups[b];22
23 return groupA === groupB;24 }25
26 /*27 * Joins two items by setting all items of the one group28 * to the same as the other group29 */30 union(a: number, b: number) {31 const groupA = this.groups[a];32 const groupB = this.groups[b];33
34 /*35 * Iterate through each item and if they are the same as B36 * then update them to be A37 */38 for (let index = 0; index < this.groups.length; index++) {39 const group = this.groups[index];40 if (group === groupB) {41 this.groups[index] = groupA;42 }43 }44 }45}
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
1export class QuickUnion {2 /*3 * Track the parent associated with each items.4 * The element is a root node if the parent is the same as the node5 */6 parents: number[];7
8 /* Initially each item is identified by a parent9 * that is the same as its own index10 */11 constructor(size: number) {12 this.parents = new Array(size).fill(0).map((_, i) => i);13 }14
15 /*16 * Get the root of a given node17 */18 root(a: number) {19 let parent = a;20 while (parent !== this.parents[a]) {21 parent = this.parents[parent];22 }23
24 return parent;25 }26
27 /*28 * If two items have the same root they are connected29 */30 connected(a: number, b: number) {31 return this.root(a) === this.root(b);32 }33
34 /*35 * Joins a node by setting its root to that of the other node36 */37 union(a: number, b: number) {38 const root = this.root(a);39 this.parents[b] = root;40 }41}
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:
- Keep track of size of each tree (number of objects)
- Balance by linking root of smaller tree to root of larger tree
1import type { UnionFind } from "./interface";2
3export class WeightedQuickUnion implements UnionFind {4 /*5 * Track the parent associated with each items.6 * The element is a root node if the parent is the same as the node7 */8 parents: number[];9
10 /*11 * The number of elements in each tree12 */13 sizes: number[];14
15 /* Initially each item is identified by a parent16 * that is the same as its own index17 */18 constructor(size: number) {19 this.parents = new Array(size).fill(0).map((_, i) => i);20
21 this.sizes = new Array(size).fill(1);22 }23
24 /*25 * Get the root of a given node26 */27 root(a: number) {28 let parent = a;29 while (parent !== this.parents[a]) {30 parent = this.parents[parent];31 }32
33 return parent;34 }35
36 /*37 * If two items have the same root they are connected38 */39 connected(a: number, b: number) {40 return this.root(a) === this.root(b);41 }42
43 /*44 * Joins a node by setting its root to that of the other node45 *46 * Differs from Quick Union by checking tree sizes and prefering a47 * smaller tree where possible48 */49 union(a: number, b: number) {50 const rootA = this.root(a);51 const rootB = this.root(b);52
53 if (rootA === rootB) {54 return;55 }56
57 const sizeA = this.sizes[rootA];58 const sizeJ = this.sizes[rootB];59 if (sizeA < sizeJ) {60 this.parents[rootA] = rootB;61 this.sizes[rootB] += sizeA;62 } else {63 this.parents[rootB] = rootA;64 this.sizes[rootA] += sizeJ;65 }66 }67}
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:
1import type { UnionFind } from "./interface";2
3export class WeightedQuickUnionPathCompression implements UnionFind {4 /*5 * Track the parent associated with each items.6 * The element is a root node if the parent is the same as the node7 */8 parents: number[];9
10 /*11 * The number of elements in each tree12 */13 sizes: number[];14
15 /* Initially each item is identified by a parent16 * that is the same as its own index17 */18 constructor(size: number) {19 this.parents = new Array(size).fill(0).map((_, i) => i);20
21 this.sizes = new Array(size).fill(1);22 }23
24 /*25 * Get the root of a given node26 */27 root(a: number) {28 let parent = a;29 while (parent !== this.parents[parent]) {30 // since we're already at this node we can just move it up a level31 parent = this.parents[this.parents[parent]];32 this.parents[parent] = parent;33 }34
35 return parent;36 }37
38 /*39 * If two items have the same root they are connected40 */41 connected(a: number, b: number) {42 return this.root(a) === this.root(b);43 }44
45 /*46 * Joins a node by setting its root to that of the other node47 *48 * Differs from Quick Union by checking tree sizes and prefering a49 * smaller tree where possible50 */51 union(a: number, b: number) {52 const rootA = this.root(a);53 const rootB = this.root(b);54
55 if (rootA === rootB) {56 return;57 }58
59 const sizeA = this.sizes[rootA];60 const sizeB = this.sizes[rootB];61 if (sizeA < sizeB) {62 this.parents[rootA] = rootB;63 this.sizes[rootB] += sizeA;64 } else {65 this.parents[rootB] = rootA;66 this.sizes[rootA] += sizeB;67 }68 }69}
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
algorithm | init | union | find |
---|---|---|---|
quick-find | N | N | 1 |
quick-union | N | N (note) | N |
weighted-quick-union | N | lg N (note) | lg N |
weighted-quick-union-pc | N | lg* N | lg N |
(note) Includes cost of finding the root