Sign in to watch this lesson
Algorithms - Graphs II · 5:23
Kruskal's Minimum Spanning Tree
To connect eight offices with the cheapest set of leased lines, we need a minimum spanning tree: no loops, exactly n - 1 lines. The cut property explains why the cheapest line across any split is safe, Kruskal's algorithm turns it into a procedure (sort by price, skip any line that closes a loop; total 31 on our graph), and a disjoint set union with union by size and path compression answers 'already connected?' in almost constant time, so the sort's O(m log m) dominates.
You will learn
- Explain why a cheapest connecting network is a spanning tree with n - 1 edges, and state the cut property with its exchange proof
- Run Kruskal's algorithm by hand: sort the edges, take an edge exactly when it joins two different components, stop after n - 1
- Implement a disjoint set union with union by size and path compression and use it to reject cycle-closing edges
- Handle disconnected graphs (IMPOSSIBLE) and 64-bit totals, and know that the sort's O(m log m) dominates