Part VI · Graph Algorithms and Tree-Graph Techniques
36. Minimum Spanning Trees and Graph Connectivity
6 lessons•24 topics•Intermediate / Advanced
6 of 6 lessons published
36.015 animated
MST definitions
- Spanning tree
- Total weight
- Cut property
- Cycle property
- Uniqueness with distinct weights
36.024 animated
Kruskal's algorithm
- Sort edges
- DSU
- Forest growth
- Disconnected minimum spanning forest
36.034 animated
Prim's algorithm
- Frontier heap
- Eager/lazy versions
- Adjacency list
- Dense graph variant
36.043 animated
MST variations
- Second-best MST
- Critical and pseudo-critical edges
- Maximum spanning tree
- MST under edge changes
36.053 animated
Connectivity under changes
- Offline connectivity
- Union-find with sorted thresholds
- Dynamic connectivity overview
36.063 animated
MST correctness
- Exchange proof
- Cut proof
- Greedy choice
- Complexity comparison