= Disjoint-set data structure
{wiki}
= Union-find
{synonym}
A <disjoint-set data structure> maintains a <partition of a set>. Its find operation returns a representative, equal for two elements exactly when they belong to the same block; its union operation merges two blocks. <Kruskal's algorithm> uses it to track <connected components of a graph>.
Start with a <singleton set> for every stored <set element>. Each <disjoint-set find operation> returns a <disjoint-set representative>; a <disjoint-set union operation> merges the containing <blocks of a set partition>. The interface does not split a <block of a set partition> or delete a member.<Algorithms, 4th edition by Robert Sedgewick and others/UF.java>[Algorithms, 4th edition by Robert Sedgewick and others; UF.java, class documentation: initial singletons, representative equality and union interface]{ref}
The <partition of a set> consists of nonempty disjoint <blocks of a set partition> covering the stored <set>; being in the same <block of a set partition> defines an <equivalence relation>. A <disjoint-set representative> names a whole <block of a set partition>, without requiring a list of its members.
Back to article page
