Minimum Spanning Trees
A minimum spanning tree connects all vertices of a weighted graph with the least total edge weight and no cycles.
Cheapest way to connect everything
Given a connected, undirected graph with edge weights, a spanning tree is a subset of edges that connects all V vertices using exactly V-1 edges and no cycles. A minimum spanning tree (MST) is a spanning tree whose total edge weight is as small as possible. It answers questions like the least amount of cable needed to connect every building on a site.
The cut property
Both standard MST algorithms rest on the cut property: for any partition of the vertices into two groups, the cheapest edge crossing between them belongs to some minimum spanning tree. This guarantees that greedily choosing safe minimum-weight edges never leads you astray, which is why greedy algorithms solve MST optimally.
- Exactly V-1 edges, connects all vertices, contains no cycle
- Cut property: the lightest crossing edge is always safe to add
- Prim's algorithm grows one tree outward
- Kruskal's algorithm adds global lightest edges
Uniqueness and ties
When all edge weights are distinct the MST is unique. If weights repeat, several minimum spanning trees may exist with the same total weight. Any of them is a valid answer, and the two algorithms may return different ones.
Where MSTs are used
Minimum spanning trees model least-cost network design, from laying utility lines to clustering data by cutting the longest tree edges. They also appear as a subroutine in approximation algorithms, such as a two-approximation for the travelling salesman problem on metric graphs. The two classic methods, Prim's and Kruskal's, differ in how they apply the cut property.