Blueprint schematic of Kruskal's minimum spanning tree algorithm

Algorithms & Data Structures

The Cheapest Way to Connect Everything Without Going in Circles

A greedy algorithm that is provably optimal — Kruskal's, and the union-find data structure that makes it fast.

Core Concept

Given a weighted network, the minimum spanning tree (MST) is the cheapest set of links that keeps every node reachable — no cycles, total cost minimised. Kruskal's finds it with a deceptively simple rule: sort every edge by weight, then take each edge if and only if it joins two components that are not already connected. What makes a greedy choice "cheap" safe here is not a lucky ordering but a structural theorem — the cut property: for any split of the vertices into two groups, the lightest edge crossing the split belongs to some MST. So accepting the cheapest edge across any current cut forecloses nothing.

Key Components

The Cut Property

For any cut of the vertices, the lightest crossing edge is in some MST. This is the entire proof that the cheapest available edge can never be a mistake.

Union-Find

Answers "are these two endpoints already connected?" in near-constant time — the question Kruskal asks on every edge.

Path Compression + Rank

Flatten chains to the root on every lookup; hang the shorter tree under the taller. Together: inverse-Ackermann, effectively constant.

The Sort Is the Cost

Connectivity checks are ~free, so the real cost of Kruskal's is the sort: O(E log E). Not the tree, the ordering.

How It Works

Sort the edges

List every edge in ascending weight order. This is the step that pays for the whole algorithm.

Walk the list, cheapest first

For each edge, ask union-find: are its endpoints in the same component yet?

Accept only crossing edges

Different components → UNION the two trees, keep the edge. Same component → accepting it would create a cycle, so skip it. By the cut property, every accepted edge is in some MST.

Stop at V − 1 edges

A tree on V vertices has exactly V − 1 edges. The moment you have them, you're done — no revisiting, no second pass.

Trap 1 — An MST is not good routes

An MST minimises the total weight of the whole structure, and says nothing about the distance between any particular pair. On a square with three sides of weight 1 and a diagonal of 1.5, the MST drops the diagonal: the MST path between those corners costs 2, while the direct 1.5 edge was sitting there the whole time. If you want distances, you want Dijkstra. If you want the cheapest set of links that keeps everything reachable, you want an MST. (The diagonal has to weigh under 2 for this to bite — at exactly 2 both routes tie and the example proves nothing.)

Trap 2 — The tie means the answer is not unique

When several edges share a weight, multiple MSTs of identical total cost can exist. Two correct implementations can return different trees — so a test that asserts a specific edge set will fail for no real reason. Assert the total weight, not the edges.

Real-World Applications

Network wiring — cheapest cabling layout Road & pipeline planning Cluster & cloud topology PCB trace routing Single-linkage clustering Approximation algorithms (MST ×2 ≈ TSP)

Checkpoint — answer before you move on

Kruskal accepts an edge only when its endpoints lie in different components. Why can that cheapest-first choice never be wrong? Reach for the cut property — what is special about the lightest edge crossing a split?
Path compression and union-by-rank each alone are not enough to guarantee near-constant operations. Why do the two tricks only work together? One controls tree height at union time, the other repairs whatever height exists at find time.
Two engineers implement Kruskal correctly and their tests disagree: each returns a different tree, both with the same total weight. Which one is wrong? Think about what happens when edges share a weight.

Hafs Ibrahim

𝕏 @hafs_darwish LinkedIn GitHub Blog

Algorithms & Data Structures • Sensei Learning System