union-find.md

UnionFind

A UnionFind data structure used to keeps track of a set of elements partitioned into a number of disjoint (non-overlapping) subsets.

API

abstract class AbstractUnionFind {
  count: number;
  constructor(...items?: any[]);
  find(item: any);
  connected(itemA: any, itemB: any): boolean;
  union((itemA: any, itemB: any);
  sets(): [][];
}

Implementations

• QuickFind
• QuickUnion

Resources

• 1.5 Case Study: Union-Find - Algorithms (4th ed)
• Disjoint Set - trekhleb/javascript-algorithms
• QuickFind.java - Algorithms (4th ed)
• QuickUnion.java - Algorithms (4th ed)
• Union Find - Union and Find Operations