03
Minimum Spanning Trees: Kruskal & Prim
Chapter 3 • Advanced
150 min
Minimum Spanning Trees: Kruskal & Prim
What is a Minimum Spanning Tree (MST)?
A spanning tree of a connected graph is a subgraph that:
- Contains all vertices
- Is a tree (connected, no cycles)
A minimum spanning tree has minimum total edge weight.
Kruskal's Algorithm
Greedy Strategy
Add edges in increasing order of weight, avoiding cycles.
Algorithm Steps
- Sort all edges by weight
- Initialize empty MST
- For each edge (in sorted order):
- If adding edge doesn't create cycle, add to MST
- Use Union-Find to detect cycles
Implementation
python.js
class UnionFind:
def __init__(self, n):
self.parent = list(range(n))
self.rank = [0] * n
def find(self, x):
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x]) # Path compression
return self.parent[x]
def union(self, x, y):
root_x = self.find(x)
root_y = self.find(y)
if root_x == root_y:
return False # Already connected
# Union by rank
if self.rank[root_x] < self.rank[root_y]:
self.parent[root_x] = root_y
elif self.rank[root_x] > self.rank[root_y]:
self.parent[root_y] = root_x
else:
self.parent[root_y] = root_x
self.rank[root_x] += 1
return True
def kruskal(vertices, edges):
"""
Kruskal's algorithm for MST.
edges: [(u, v, weight), ...]
Time: O(E log E), Space: O(V)
"""
# Sort edges by weight
edges.sort(key=lambda x: x[2])
uf = UnionFind(vertices)
mst = []
mst_weight = 0
for u, v, weight in edges:
if uf.union(u, v):
mst.append((u, v, weight))
mst_weight += weight
if len(mst) == vertices - 1:
break # MST complete
return mst, mst_weight
Prim's Algorithm
Greedy Strategy
Start from arbitrary vertex, repeatedly add minimum-weight edge connecting tree to new vertex.
Algorithm Steps
- Start with arbitrary vertex
- Maintain set of vertices in MST
- Use priority queue for edges connecting tree to outside
- Repeatedly add minimum-weight edge
Implementation
python.js
import heapq
def prim(graph, start=0):
"""
Prim's algorithm for MST.
graph: adjacency list [(neighbor, weight), ...]
Time: O((V + E) log V), Space: O(V)
"""
n = len(graph)
visited = [False] * n
mst = []
mst_weight = 0
# Priority queue: (weight, from, to)
pq = [(0, -1, start)]
while pq and len(mst) < n - 1:
weight, from_vertex, u = heapq.heappop(pq)
if visited[u]:
continue
visited[u] = True
if from_vertex != -1:
mst.append((from_vertex, u, weight))
mst_weight += weight
for v, w in graph[u]:
if not visited[v]:
heapq.heappush(pq, (w, u, v))
return mst, mst_weight
Comparison
| Feature | Kruskal | Prim |
|---|---|---|
| Data Structure | Union-Find | Priority Queue |
| Best for | Sparse graphs | Dense graphs |
| Time | O(E log E) | O((V+E) log V) |
| Space | O(V) | O(V) |
| Implementation | Simpler | More complex |
Applications
- Network design: Connect cities with minimum cost
- Clustering: Group similar data points
- Approximation algorithms: TSP approximation
- Image segmentation: Connect similar pixels
Practice Problems
- Find MST using both algorithms
- Count number of MSTs
- Second-best MST
- Minimum cost to connect all cities
- MST with constraints