Day 22 — Minimum Spanning Trees

What you’ll learn here

• Kruskal’s algorithm — sort edges, add the cheapest that doesn’t form a cycle (relies on Union Find)
• Prim’s algorithm — grow the tree out from one vertex using a priority queue
• The cut property and the cycle property — why both greedy approaches actually work
• Applications: network design, clustering, image segmentation

An MST connects every vertex with the minimum total edge weight — and it’s one of the rare optimization problems where a greedy algorithm is provably optimal.