DSA · Chapter 29 of 40
Minimum Spanning Tree
A minimum spanning tree connects every vertex of a weighted undirected graph with the smallest possible total edge weight and no cycles. It has exactly V - 1 edges.
Kruskal's algorithm sorts all edges and adds the cheapest that does not create a cycle (using union-find). Prim's algorithm grows a single tree, always adding the cheapest edge leaving it, using a min-heap.
Kruskal
Sort edges O(E log E), then union-find each edge. Best for sparse graphs and easy to reason about.
Prim
Start from any vertex and repeatedly pull the cheapest crossing edge from a heap — O(E log V). Better for dense graphs.
Example 1 (python)
edges = [(1, 'A', 'B'), (4, 'A', 'C'), (2, 'B', 'C')]
edges.sort()
parent = {'A': 'A', 'B': 'B', 'C': 'C'}
def find(x):
while parent[x] != x:
x = parent[x]
return x
total = 0
for w, u, v in edges:
ru, rv = find(u), find(v)
if ru != rv:
parent[ru] = rv
total += w
print(total)Output
3Kruskal picks edges A-B (1) and B-C (2).
Example 2 (python)
# an MST on V vertices always has V-1 edges
V = 3
print('MST edges =', V - 1)Output
MST edges = 2A useful sanity check on any MST answer.
Key points
- An MST has V - 1 edges and no cycles.
- Kruskal sorts edges and uses union-find.
- Prim grows one tree with a min-heap.
- MSTs apply to undirected weighted graphs.
💡 Note: Network cabling and clustering problems are usually MST problems.