MST Ladder¶
MST practice should build the instinct that “connect everything cheaply” is a different goal from shortest paths, and that Kruskal is really a sorted greedy plus DSU invariant.
Who This Is For¶
Use this ladder if:
- weighted graph problems still blur together
- Kruskal feels like a memorized recipe instead of a justified greedy
- you forget to check whether the graph is actually connectable
Warm-Up¶
- Kruskal on small undirected graphs
- detect whether all vertices become connected
Target skill:
- understand why each chosen edge is safe
Core¶
- MST with DSU
- compare Kruskal and Prim
Target skill:
- choose the algorithm from the graph representation and proof style
Stretch¶
- threshold or clustering problems built on MST
- use MST edges for later reasoning about bottlenecks
Target skill:
- treat MST as a reusable subroutine, not just a standalone task
Exit Criteria¶
You are ready to move on when:
- you can explain the cut-property intuition in plain language
- you never confuse MST with shortest paths
- you remember to verify full connectivity