Algorithms / Mst Greedy
Least You Need to Know: Minimum Spanning Trees, Safe Edges, and Greedy Structure
Minimum spanning tree problems are a flagship example of provably correct greedy reasoning. The key concepts are cut-safe edges, the difference between tree weight and shortest-path objectives, and the way Kruskal and Prim each exploit a local choice rule that is globally safe.
The least you need to know
- An MST is a minimum-total-weight spanning tree of a connected weighted undirected graph.
- The cut property explains why certain light edges are safe to add.
- Kruskal grows a forest by adding safe edges in increasing weight order while avoiding cycles.
- Prim grows one tree by repeatedly adding the cheapest edge leaving the current tree.
- MST objectives minimize total tree weight, not path lengths from a source.
Key notation
MST
minimum spanning tree
safe edge
an edge that can be added while preserving the possibility of optimality
cut property
the lightest edge crossing a cut is safe for some MST
Tiny worked example
- In Kruskal's algorithm, sort edges by weight.
- Add the next lightest edge that connects two different components.
- The cut property justifies each safe choice.
- Stop once the graph has `n-1` chosen edges and is connected.
Common mistakes
- Students often confuse MST with shortest-path trees because both are trees in weighted graphs.
- Negative weights do not break MST algorithms in the way they can break Dijkstra.
- The graph is typically undirected for standard MST formulations.
How to recognize this kind of problem
- The prompt asks for minimum total connection cost over all vertices.
- Safe edge or cut language appears in the proof.
- You are building a tree, not optimizing paths from one source.