Kruskal's Minimum Spanning Tree
Add cheapest edges without cycles.
What an MST Is
A minimum spanning tree connects every vertex using the cheapest total edge weight, with no cycles. Think wiring a town for the least cost. 🌲
Kruskal's Core Idea
Kruskal's algorithm is pure greed: keep adding the cheapest edge that does not create a cycle until the whole graph is joined.
All lessons in this course
- DSU with Path Compression
- Union by Rank and Components
- Kruskal's Minimum Spanning Tree
- Prim's MST with a Heap