Clayton

Posted on May 5, 2020 • Originally published at thefrugal.dev

Disjoint-Set/Union-Find Data Structure

#datastructures #algorithms #disjointset #unionfind

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 Union command and the Find query, which we'll go into more detail below.

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 Union command)
- Determine if there is a path connecting the two objects (the Find query)

Union-Find Illustration

Quick Find

Quick Find is an Eager algorithm also used to solve the dynamic connectivity problem.
The Find query for this algorithm is very efficient and is measured in constant time.
- Given id[] of size N, check if p and q are connected.
The Union 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.
- When changing a value of id[q], you must also change all entries whose value is equal (connected) to id[q] as well.

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 Find query requires a traversal up the tree:
- Given id[] of size N, check if p and q have the same root.
The Union command requires the 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.

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 a Union operation is performed, we will always link the root of the smaller tree to the root of the larger tree.
- 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 Find query takes the time proportional to the depth of 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).

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 Union operation, however, we are incrementing the size of the larger root by the size of the smaller root.

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.

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;
}

DEV Community