Union-Find
Union-Find is a datastructure used in Kruskal's algorithm that maintains equivalence classes as undirected graphs composed of vertices representing the set elements, such that two vertices appear in the same connected component of the graph if and only if the vertices are equivalent. A Union-Find datastructure supports at least the Find and Union operations. Find returns the equivalence class of a given element, and Union merges two equivalence classes into a single class.
Implementation
Union-Find is often implemented as a Forest of trees. Each individual tree consists of a number of vertices with parent pointers. Thus, the Find operation traverses the tree and returns the root, and the Union operation adds one tree to another. When implemented as a tree, two simple optimizations are often performed to increase performance:
- Path Compression: When a Find operation is performed, the node on which the find was called replaces its parent pointer with a pointer to the root. The next time Find is called on that node, direct lookup occurs.
- Balancing: If you always merge a smaller tree to the larger tree when Union is called, the tree does not become unbalanced and linear.