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

1
0---1   2   3---4
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

1
export 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:

1
import type { UnionFind } from "./interface";
2

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

9
  /* Initially each item is identified by a group
10
   * that is the same as its own index
11
   */
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 same
18
   */
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 group
28
   * to the same as the other group
29
   */
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 B
36
     * then update them to be A
37
     */
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

1
export 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 node
5
   */
6
  parents: number[];
7

8
  /* Initially each item is identified by a parent
9
   * that is the same as its own index
10
   */
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 node
17
   */
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 connected
29
   */
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 node
36
   */
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

1
import type { UnionFind } from "./interface";
2

3
export 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 node
7
   */
8
  parents: number[];
9

10
  /*
11
   * The number of elements in each tree
12
   */
13
  sizes: number[];
14

15
  /* Initially each item is identified by a parent
16
   * that is the same as its own index
17
   */
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 node
26
   */
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 connected
38
   */
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 node
45
   *
46
   * Differs from Quick Union by checking tree sizes and prefering a
47
   * smaller tree where possible
48
   */
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:

1
import type { UnionFind } from "./interface";
2

3
export 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 node
7
   */
8
  parents: number[];
9

10
  /*
11
   * The number of elements in each tree
12
   */
13
  sizes: number[];
14

15
  /* Initially each item is identified by a parent
16
   * that is the same as its own index
17
   */
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 node
26
   */
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 level
31
      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 connected
40
   */
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 node
47
   *
48
   * Differs from Quick Union by checking tree sizes and prefering a
49
   * smaller tree where possible
50
   */
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