Kruskal and disjoint sets

A campus needs cables connecting every building, and contractors have quoted costs for possible links. The objective is the total installation bill, not the shortest route from the entrance to each building.

Taking the cheapest links blindly can buy a cheap cycle while leaving a building isolated. Kruskal considers links in cost order but accepts one only when it joins two currently separate components. Union-find makes that connectivity check cheap.

Connecting every building on a budget

Kruskal builds a minimum spanning tree by considering the cheapest candidate edges first and accepting only edges joining separate components. Simply choosing the cheapest V-1 edges can form a cycle while leaving another vertex disconnected. Connectivity is the condition that makes greedy selection safe.

A baseline stores the accepted forest and runs DFS/BFS for each candidate to check whether its endpoints already connect. Disjoint sets replace those repeated traversals with a compact component index.

Rejecting a cheap edge that closes a cycle

Each vertex starts as its own parent/root. find follows parents; two vertices are connected exactly when their roots match. Union must join roots, not arbitrary endpoints. Union by size attaches the smaller component's root below the larger; path compression shortens future find walks. DSU links describe bookkeeping, not the actual graph edges, so keep accepted edges separately.

The cut property proves a chosen cheapest cross-component edge is safe. Adding it to an optimal spanning tree creates a cycle; replacing another no-cheaper edge crossing the same cut preserves connectivity without increasing cost. Negative edge weights do not invalidate this argument. A self-loop never joins two components.

Normalize endpoint order before sorting, and compare candidates by weight, lower endpoint, then upper endpoint. Default array sort is not that comparator. Return accepted edges in their selection order. Fewer than V-1 accepted edges means no spanning tree; a minimum spanning forest is a different API.

const [u, v, weight] = [3, 1, -2];
const normalized = [Math.min(u, v), Math.max(u, v), weight];
console.log(normalized); // [1, 3, -2]
const parents = Array.from({length: 4}, (_, index) => index);
console.log(parents); // [0, 1, 2, 3]: initially separate components

Keeping component links separate from cables

Sorting plus compressed, size/rank-balanced DSU costs O(V + E log(E+1)) overall under the usual near-constant amortized DSU bound, with O(V+E) space including copied candidates. Repeated forest searches add O(EV) worst-case work. Use Kruskal for edge-list connection cost, Prim for a useful frontier representation, and shortest-path algorithms for travel costs from a source.

The cable plan consists of the accepted graph edges, never the DSU parent links used to choose them.