Minimum Spanning Tree
The subset of edges connecting all vertices in a weighted graph at the lowest possible total cost
A Minimum Spanning Tree (MST) is a subset of edges from a connected, weighted, undirected graph that connects all vertices together, without cycles, at the minimum possible total edge weight.
Definition
A Minimum Spanning Tree (MST) is a subset of edges from a connected, weighted, undirected graph that connects all vertices together, without cycles, at the minimum possible total edge weight.
Overview
A spanning tree of a connected graph with n vertices is any subset of n-1 edges that connects every vertex without forming a cycle — the minimum number of edges needed to keep the graph connected. When edges carry weights, typically representing cost, distance, or capacity, many different spanning trees are usually possible, and the minimum spanning tree is the one among them with the lowest total edge weight. If any two edge weights are distinct, the MST is guaranteed to be unique; ties can produce multiple valid minimum spanning trees with the same total weight. Two classic greedy algorithms solve MST optimally, and both rely on the same underlying insight, sometimes called the cut property: for any partition of a graph's vertices into two groups, the minimum-weight edge crossing between them must belong to some minimum spanning tree. Kruskal's algorithm sorts all edges by weight and greedily adds each one, skipping any edge that would create a cycle, using a Union-Find data structure to check connectivity efficiently, giving a total time of O(E log E). Prim's algorithm instead grows a single tree outward from an arbitrary starting vertex, repeatedly adding the cheapest edge that connects a vertex already in the tree to one that isn't, typically implemented with a priority queue for O(E log V) time. MST problems appear directly in network design — laying cable or fiber to connect a set of locations at minimum total cost, designing efficient road or utility networks — and as a building block inside more complex algorithms, including certain approximation algorithms for the traveling salesman problem, cluster analysis, and image segmentation. Because both Kruskal's and Prim's algorithms are conceptually simple, provably optimal, and efficient, MST is one of the cleaner examples in algorithms coursework of a greedy strategy that actually guarantees a globally optimal answer, in contrast to problems like the knapsack problem where naive greedy approaches fail.
Key Concepts
- Connects all vertices of a weighted graph with minimum total edge weight
- Uses exactly n-1 edges for n vertices and contains no cycles
- Unique if all edge weights are distinct; ties can allow multiple valid MSTs
- Relies on the cut property: the minimum crossing edge always belongs to some MST
- Solved optimally by Kruskal's algorithm using sorted edges and Union-Find
- Solved optimally by Prim's algorithm using a priority queue to grow the tree
- A rare example where a purely greedy strategy guarantees global optimality
- Building block for TSP approximation, clustering, and network design algorithms