Implementing Disjoint Set Union with Path Compression in JavaScript

The Disjoint Set Union data structure—often referred to as Union-Find—is a fundamental algorithm for managing partitions across a collection of elements. It answers two primary questions in dynamic graphs: which disjoint subset does an element belong to, and how can two separate subsets be joined together.

In web applications dealing with collaborative canvas tools, peer-to-peer network mesh discovery, or graph-based UI relationship trees, determining whether two nodes share a connected path without repeatedly traversing the entire graph via breadth-first search is critical for interactive frame rates.

A naive tree-based disjoint set implementation risks degrading to linear $O(n)$ search time if elements form a single degenerated linked list. By implementing two crucial optimizations—path compression during lookup and union by rank during consolidation—the amortized runtime drops to $O(\alpha(n))$, where $\alpha$ is the inverse Ackermann function. In practice, this value remains less than 5 for any conceivable dataset, rendering operations practically constant time.

Example #

// Detect cycles in an undirected graph representation
const edges = [
  ['ClientA', 'Gateway1'],
  ['Gateway1', 'ClusterPrimary'],
  ['ClusterPrimary', 'Worker3'],
  ['Worker3', 'ClientA'], // Introducing this edge closes a network loop
];

const network = new DisjointSet();
let loopDetected = false;

for (const [source, destination] of edges) {
  if (network.connected(source, destination)) {
    console.warn(`Redundant connection detected forming cycle between ${source} and ${destination}`);
    loopDetected = true;
    break;
  }
  network.union(source, destination);
}

console.log(`Total connected networks: ${network.count}`);
console.log(`Is ClientA connected to Worker3? ${network.connected('ClientA', 'Worker3')}`);

Implementation #

/**
 * Disjoint Set Union (Union-Find) with Path Compression and Union by Rank.
 * Supports arbitrary element keys via ES2015 Map storage.
 */
class DisjointSet {
  constructor() {
    // Maps each element to its direct parent representative
    this.parents = new Map();
    // Maps root representatives to their tree rank (approximate tree height)
    this.ranks = new Map();
    // Tracks the total number of distinct disjoint sets
    this.setsCount = 0;
  }

  /**
   * Initializes an element as its own representative if not previously registered.
   * @param {*} item - Unique identifier for the element.
   */
  makeSet(item) {
    if (!this.parents.has(item)) {
      this.parents.set(item, item);
      this.ranks.set(item, 0);
      this.setsCount += 1;
    }
  }

  /**
   * Finds the representative root of the set containing item.
   * Employs two-pass path compression to flatten the parent tree.
   * @param {*} item - The item to look up.
   * @returns {*} The canonical root representative.
   */
  find(item) {
    this.makeSet(item);

    let root = item;
    while (root !== this.parents.get(root)) {
      root = this.parents.get(root);
    }

    // Path compression: flatten the path directly to the discovered root
    let current = item;
    while (current !== root) {
      const next = this.parents.get(current);
      this.parents.set(current, root);
      current = next;
    }

    return root;
  }

  /**
   * Merges the sets containing itemA and itemB using union by rank.
   * @param {*} itemA - First element.
   * @param {*} itemB - Second element.
   * @returns {boolean} True if sets were merged; false if they were already in the same set.
   */
  union(itemA, itemB) {
    const rootA = this.find(itemA);
    const rootB = this.find(itemB);

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

    const rankA = this.ranks.get(rootA);
    const rankB = this.ranks.get(rootB);

    // Attach the shallower tree under the deeper tree
    if (rankA < rankB) {
      this.parents.set(rootA, rootB);
    } else if (rankA > rankB) {
      this.parents.set(rootB, rootA);
    } else {
      this.parents.set(rootB, rootA);
      this.ranks.set(rootA, rankA + 1);
    }

    this.setsCount -= 1;
    return true;
  }

  /**
   * Checks if two elements belong to the same connected component.
   * @param {*} itemA - First element.
   * @param {*} itemB - Second element.
   * @returns {boolean}
   */
  connected(itemA, itemB) {
    return this.find(itemA) === this.find(itemB);
  }

  /**
   * Returns current count of disjoint sets.
   * @returns {number}
   */
  get count() {
    return this.setsCount;
  }
}

Main Point: Combining path compression with union by rank gives the Disjoint Set Union data structure nearly constant amortized time complexity for connectivity checks and dynamic cycle detection.

Credits #

Photo by Chalo Garcia on Unsplash

← Home