61B-30: Minimum Spanning Trees
Contents
warm up
MST, Cut Property, Generic MST Algorithm
MST vs SPT
A shortest paths tree depends on the start vertex:
- Because it tells you how to get from a source to EVERYTHING.
There is no source for a MST.
Nonetheless, the MST sometimes happens to be an SPT for a specific vertex.
两者关系不大？
Cut Property
简单证明 cross bridge 一定在 MST 中。
Generic MST Algorithm
Start with no edges in the MST.
- Find a cut that has no crossing edges in the MST.
- Add smallest crossing edge to the MST.
- Repeat until V-1 edges.
This should work, but we need some way of finding a cut with no crossing edges!
- Random isn’t a very good idea.
Prim’s Algorithm
Prim’s vs. Dijkstra’s
Prim’s and Dijkstra’s algorithms are exactly the same, except Dijkstra’s considers “distance from the source”, and Prim’s considers “distance from the tree.”
Visit order:
- Dijkstra’s algorithm visits vertices in order of distance from the source.
- Prim’s algorithm visits vertices in order of distance from the MST under construction.
Relaxation:
- Relaxation in Dijkstra’s considers an edge better based on distance to source.
- Relaxation in Prim’s considers an edge better based on distance to tree.
pseudocode
runtime
Kruskal’s Algorithm
Kruskal’s Algorithm Pseudocode
runtime
Summary
SOTA of compare-based MST algorithms 🆙