Minimum Spanning Tree — Kruskal's (Union-Find), Prim's (priority queue)
The one theorem that makes greed work
Kruskal's algorithm — "sort edges, add if no cycle"
HOW do we test "same component fast"? → Union-Find (DSU)
class DSU:
def __init__(self, n):
self.p = list(range(n))
self.r = [0]*n # rank ~ tree height
def find(self, x):
while self.p[x] != x:
self.p[x] = self.p[self.p[x]] # path compression (halving)
x = self.p[x]
return x
def union(self, a, b):
ra, rb = self.find(a), self.find(b)
if ra == rb: return False # already connected -> would make cycle
if self.r[ra] < self.r[rb]: ra, rb = rb, ra
self.p[rb] = ra
if self.r[ra] == self.r[rb]: self.r[ra] += 1
return True
def kruskal(n, edges): # edges: list of (w,u,v)
dsu = DSU(n); total = 0; mst = []
for w,u,v in sorted(edges): # WHY sort: process lightest first (greedy)
if dsu.union(u,v): # WHY: union returns False if same component
total += w; mst.append((u,v,w))
if len(mst) == n-1: break # WHY: a tree on n nodes needs exactly n-1 edges
return total, mstTime: (dominated by the sort) .
Prim's algorithm — "grow one tree from a seed"
HOW to get the cheapest crossing edge fast → min-heap (priority queue)
def prim(n, adj, start=0): # adj[u] = list of (w,v)
import heapq
visited = [False]*n
pq = [(0, start)] # (edge weight to reach node, node)
total = 0; cnt = 0
while pq and cnt < n:
w, u = heapq.heappop(pq) # WHY heap: pop the globally cheapest frontier edge
if visited[u]: continue # WHY: lazy deletion — stale heap entries skipped
visited[u] = True; total += w; cnt += 1
for ew, v in adj[u]:
if not visited[v]:
heapq.heappush(pq, (ew, v)) # WHY: v is now reachable across the cut
return totalTime: lazy heap ; with a decrease-key / indexed heap ; with a Fibonacci heap .
Worked example (same graph, both algorithms)
Vertices . Edges: .
Kruskal:
| Step | Edge | Action | Why |
|---|---|---|---|
| 1 | (0,1,1) | add | lightest; 0,1 in different sets |
| 2 | (1,2,2) | add | 1,2 different sets |
| 3 | (0,2,3) | skip | 0 and 2 already same component → cycle |
| 4 | (2,3,4) | add | 2,3 different sets → now 3 edges (V−1) → stop |
MST weight . Why skip step 3? Adding it joins two vertices already connected — a cycle, never in an MST.
Prim from 0: heap pops (w0) → push (1,1),(3,2),(5,3). Pop (1,1) → push (2,2). Pop (2,2) → push (4,3). Pop (4,3). Total . Why same answer? Both obey the cut property; the MST weight is unique even if the tree isn't.
Recall Feynman: explain to a 12-year-old
Imagine islands you must connect with bridges, and every bridge costs money. You want all islands joined for the least cash, and you never build a useless bridge that just loops back to islands already linked. Kruskal: look at all possible bridges from cheapest to dearest; build one only if it joins two not-yet-connected groups. Prim: start on one island and keep adding the cheapest bridge that reaches a brand-new island. Both end up spending the same minimum total.
Connections
- Disjoint Set Union (Union-Find) — the engine inside Kruskal.
- Priority Queue (Binary Heap) — the engine inside Prim.
- Dijkstra's Algorithm — same heap skeleton as Prim, but key = path distance, not edge weight.
- Cut Property and Cycle Property — the correctness backbone.
- Greedy Algorithms — exchange-argument proof pattern.
- Graph Representations — edge list (Kruskal) vs adjacency list (Prim).
What does the cut property guarantee?
Why is the lightest edge of a cycle never needed in an MST?
In Kruskal, what does Union-Find decide?
Two Union-Find optimizations and their effect?
Time complexity of Kruskal and why?
Time complexity of Prim with a binary heap?
In Prim's lazy heap, why pop-then-skip-visited works?
Do MST algorithms work with negative edge weights?
Why don't Kruskal/Prim apply to directed graphs?
How many edges does an MST of V vertices have?
What is the difference between Prim's heap key and Dijkstra's?
When prefer Kruskal vs Prim?
Concept Map
Hinglish (regional understanding)
Intuition Hinglish mein samjho
Socho tumhare paas kuch shaher hain aur unko jodne wali sadkein, har sadak ka apna cost hai. Tumhe sabko jodna hai sabse kam paise mein, aur koi faaltu loop (cycle) nahi banana — kyunki cycle ka sabse mehenga edge hamesha hata sakte ho bina disconnect kiye. Yahi sabse sasta jodne wala tree Minimum Spanning Tree hai, jisme exactly edges hote hain.
Dono algorithms greedy hain aur dono ek hi sachhai pe khade hain: cut property. Cut matlab vertices ko do groups mein baant do; us cut ko cross karne wala sabse halka edge hamesha kisi MST mein hota hai — proof mein hum dikhate hain ki agar woh edge MST mein nahi hai to swap karke total kam (ya barabar) kar sakte hain. Kruskal: saare edges weight se sort karo, cheapest se shuru, edge tabhi lo jab uske dono ends alag component mein hon (warna cycle banega). Ye "alag component?" wala check Union-Find (DSU) karta hai — path compression aur union by rank ke saath almost constant time. Prim: ek vertex se start karo, aur baar-baar woh cheapest edge add karo jo tumhare current tree se bahar nikalta hai — ye cheapest edge min-heap (priority queue) se nikalta hai.
Important baatein: MST sirf undirected graph ke liye hai (directed ke liye Edmonds chahiye), aur negative weights se koi problem nahi kyunki hum sirf compare/sort karte hain, Dijkstra ki tarah path relax nahi karte. Kruskal (sorting bhaari), Prim heap ke saath . Sparse graph aur edge-list ho to Kruskal, dense / adjacency-list ho to Prim behtar lagta hai. Yaad rakhna: MST ka total weight unique hota hai, lekin tree shape alag ho sakta hai agar kuch weights barabar hon.