Minimum Spanning Tree
A minimum spanning tree or MST of a connected weighted graph is a subset of edges that connects every node with no cycles and the smallest possible total weight. It is the cheapest way to wire everything together.
Two classic algorithms
- Kruskal sorts all edges by weight and adds them one at a time, skipping any edge that would form a cycle. A union find structure detects cycles quickly.
- Prim grows a single tree from a starting node, repeatedly adding the cheapest edge that reaches a node not yet in the tree, using a priority queue.
Both rely on the cut property, which says the lightest edge crossing any partition of the nodes is safe to include in some MST.
Uses
MSTs model network cabling, clustering, and approximations for harder routing problems. If edge weights are all distinct the MST is unique.
Key idea
Greedily add the cheapest safe edge that avoids a cycle until every node is connected.