Algorithms
MST: Minimum Spanning Tree
Цели урока
- Understand the MST problem
- Implement Kruskal with Union-Find
- Implement Prim with a priority queue
- Know when to use each algorithm
Предварительные знания
- Graphs
- Union-Find
You're designing an electrical grid for a village. You need to connect all houses with the minimum total wire length. This is the classic MST problem, solved back in 1926!
- Network design (electrical, telecommunications)
- Data clustering
- Approximation algorithm for TSP
- Image segmentation
Borůvka's power grid and the algorithms that followed
The MST problem started with a real engineering question. In 1926 the Czech mathematician Otakar Borůvka was asked how to lay out an electrical grid for Moravia using the least total wire, and he published the first MST algorithm to answer it, years before graph theory had settled into a field. His method merges components in parallel rounds, which is why it has come back into fashion for parallel and distributed computing. In 1930 his countryman Vojtěch Jarník described the grow-from-one-vertex approach. That same algorithm was rediscovered by Robert Prim in 1957 and again by Dijkstra in 1959, so 'Prim's algorithm' is more properly Jarník-Prim. Joseph Kruskal published his sort-the-edges approach in 1956 in a four-page paper. Three classic algorithms, three different strategies, all solving the identical problem, and all justified by the same cut property: the lightest edge crossing any cut is safe to add to the MST.
Idea: Connect Everything with Minimum Weight
**Problem:** connect all vertices so that the sum of edge weights is minimal.
**MST properties:**
- Contains exactly V-1 edges (it's a tree)
- Connects all V vertices
- Has the minimum total weight
- May not be unique (when weights are equal)
**Greedy choice works!** At each step, pick the 'best' edge - and get a global optimum. This is rare!
An MST for a graph with V vertices contains:
Kruskal's Algorithm
You have a list of all possible roads between cities, sorted by construction cost. Kruskal's approach is beautifully simple: **start building with the cheapest road**. If two cities are already connected (directly or through other roads) - skip that road, it would just create a useless loop. Keep going until all cities are connected.
**Kruskal's idea:** sort edges by weight and greedily include each one if it doesn't form a cycle.
| Operation | Complexity |
|---|---|
| Sort edges | O(E log E) |
| E Union-Find operations | O(E α(V)) ≈ O(E) |
| Total | O(E log E) = O(E log V) |
Why does Kruskal use Union-Find?
Prim's Algorithm
Picture paint spreading across a map from a single city. At each step, the 'blob' expands to the nearest unpainted city. The connecting edge becomes part of the tree. **Prim's algorithm** works exactly this way - the tree grows like a living organism, always absorbing its nearest neighbor.
**Prim's idea:** grow the tree from one vertex by adding the cheapest edge connecting to the 'cloud'.
| Prim Implementation | Complexity |
|---|---|
| Naive (array) | O(V²) |
| Binary Heap | O((V + E) log V) |
| Fibonacci Heap | O(E + V log V) |
Prim resembles Dijkstra. What's the difference?
Kruskal vs Prim
| Kruskal | Prim | |
|---|---|---|
| Approach | Global (all edges) | Local (grow a tree) |
| Data structure | Union-Find | Priority Queue |
| Sparse graph | Better: O(E log E) | Worse: O(E log V) |
| Dense graph | Worse: O(V² log V) | Better: O(V²) naive |
| Parallelization | Harder | Easier |
**Applications of MST:**
- **Network design:** minimum cable length
- **Clustering:** remove k-1 heaviest MST edges → k clusters
- **Approximation algorithms:** TSP approximation via MST
- **Computer vision:** image segmentation
For a road network graph (V=10000, E=30000), better to use:
MST - Minimum Spanning Tree
- V-1 edges connecting all vertices
- Kruskal: sort + Union-Find, O(E log E)
- Prim: priority queue, O((V+E) log V)
- Kruskal better for sparse, Prim for dense
- Greedy choice gives global optimum!
Related Topics
MST is connected to many graph algorithms.
- Union-Find — Used in Kruskal
- Dijkstra — Similar to Prim
- Borůvka's Algorithm — Parallel MST
Связанные уроки
- ds-18-union-find — Kruskal relies on union-find to detect cycles
- ds-16-graphs-intro — MST is defined over weighted connected graphs
- alg-20-greedy — Prim and Kruskal are textbook greedy algorithms
- alg-14-dijkstra — Prim's frontier expansion mirrors Dijkstra's