When connections arrive one at a time, we may need to ask whether two objects are already connected without repeatedly traversing the whole graph. Union–find maintains a partition into disjoint sets and merges sets as new connections arrive.
Reading route¶
Partitions and representatives: specify what
find,unionandconnectedmean.Parent forests: follow references to a root and distinguish representation links from graph edges.
Union by size and path compression: read a complete implementation and justify its costs.
Connectivity, cycle checks and limits: connect the structure to Kruskal and identify what it cannot answer.
Review arrays and references, connected components, and amortised analysis. This topic is a prerequisite for the Kruskal implementation in the following topic.
The code manages a fixed universe of integer indices 0..n-1. It preserves the additional lecture’s tie rule: if root sizes are equal, the first argument’s root remains the root. This makes its traces reproducible; the abstract partition does not depend on which representative is chosen.
Common interface and implementation choices¶
The fixed-universe contract includes root/merge/connectivity operations, element count, component count, component size and emptiness. The operation table compares plain forests, weighted linking and compression, separating individual calls from amortised sequences.
Read element count, component count and component size as three different observations. The components field is also used by Kruskal to report the number of trees in its result. Arbitrary insertion, deletion/splitting, rollback, routes and automatic member enumeration remain outside this class.
Code listings offer Python, JavaScript and Julia tabs where a runnable example is present. Python remains the explanation and trace language; see the language guide for native conventions and runnable topic downloads.