Connecting Everything at Minimum Cost
Imagine you need to connect ten cities with fibre-optic cable and you want to minimize the total length of cable used. You don't need every city connected to every other — just that you can reach any city from any other. This is exactly the minimum spanning tree problem, one of the oldest and most practical problems in combinatorial optimization, with roots going back to Borůvka's 1926 algorithm for electrifying Moravia.
Kruskal's Greedy Strategy
Joseph Kruskal published his elegantly simple algorithm in 1956. Sort all edges by weight. Walk through them in order. If an edge connects two previously disconnected components, include it; if it would create a cycle, skip it. The key data structure is union-find (disjoint set), which answers 'are these two nodes already connected?' in nearly constant time using path compression and union by rank.
Why Greedy Works Here
Not every optimization problem yields to greedy algorithms, but MST does — provably. The cut property guarantees that the lightest edge crossing any cut of the graph must belong to some MST. Since Kruskal's algorithm always adds the globally lightest edge that doesn't form a cycle, every addition respects the cut property. This is one of the cleanest proofs of greedy correctness in all of computer science.
MSTs in the Real World
Beyond network design, MSTs appear in surprising places. In biology, they approximate phylogenetic trees. In computer vision, they segment images by clustering pixels. Single-linkage hierarchical clustering is equivalent to building an MST and cutting its heaviest edges. And the MST gives a quick 2-approximation for the metric travelling salesman problem — a result that connects this elegant structure to one of the hardest problems in mathematics.