Union-Find and Minimum Spanning Trees

We use finite, connected, undirected graphs. A tree is connected and has no cycles: exactly one simple path joins each pair of vertices. A simple path does not repeat a vertex. A spanning tree includes every vertex and uses only edges of the original graph. Having the expected number of edges alone does not prove that a graph is a tree; it must also be connected.

A tree with n vertices has n - 1 edges. Start with n separate vertices. Each edge joining different components reduces the component count by one. Reaching one component takes n - 1 joins. A spanning tree therefore keeps n - 1 edges. From an original graph with m edges, it deletes m - (n - 1) edges while preserving connectivity.

Kruskal finds a spanning tree with minimum total edge weight. Sort edges from lightest to heaviest. Accept an edge only if its endpoints are in different components; otherwise it would create a cycle. Merge the components after accepting it. Equal-weight edges may be considered in either order. Stop after n - 1 accepted edges, or scan the rest and reject them. Add only accepted weights to find the tree's total.

Union-find stores each set as a rooted parent tree. Initially each vertex is its own root. find follows parents to the root. Equal roots mean equal sets. union links different roots; if the roots match, nothing changes. During Kruskal, these sets track accepted-edge components, not all input edges. Equal roots mean a new edge would create a cycle. Parent links are bookkeeping links and need not be input edges. Different roots do not rule out an input-graph path.

Full path compression makes every visited non-root vertex point directly to the root. Suppose V points to U, U to R, and R to root P. After find(V), V and U point to P; R already did. Vertices outside the visited path keep their parents. Compression changes neither the root nor set membership. A later find(V) follows one parent link.

Union by size links the smaller set's root under the larger set's root. Ties allow either root. Each depth increase at least doubles a vertex's set size, so find takes O(log n) worst-case time. Adding path compression gives O(alpha(n)) amortised time per find or union, where alpha is the slowly growing inverse Ackermann function. The bound applies across a sequence; it does not promise constant time for each call.

A cut divides all vertices into two nonempty groups. Suppose accepted forest F is contained in some minimum spanning tree (MST), and no edge of F crosses the cut. A lightest crossing edge E is safe: some MST contains both F and E. Kruskal uses one current component as a group. Its next accepted edge is lightest across that cut. With ties, 'lightest' can describe several edges; different choices can produce different MSTs.

Use an exchange argument. Take an MST T containing F. If T lacks E, adding E creates one cycle. Another edge H on that cycle crosses the cut. H is not in F, since no edge of F crosses. Remove H from the cycle. The result is a spanning tree keeping F and E. E weighs no more than H, so the total cannot rise. The resulting tree is also minimum.