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