On this page
Description
A minimum spanning tree (MST) connects every node with the cheapest set of edges, like cable between buildings. It is always a tree with V - 1 edges: a cycle would hold an edge you could drop. Two greedy algorithms find it. Kruskal's takes the cheapest edges that don't close a cycle. Prim's grows one tree from a start node.
We'll go from simple to more technical:
- The pattern: Kruskal's with union-find, and Prim's with a heap.
- A second flavor: array-based Prim's for dense graphs.
- Where MSTs are used in production (networks, clustering, approximations).
- What breaks it: stale heap entries, slow cycle checks, overwritten keys, disconnected graphs.
The approach
Kruskal's sorts the edges by weight and takes each one whose ends aren't connected yet. Here it is on four nodes with edges 0-1 (1), 1-2 (2), 0-2 (3), 2-3 (4) and 1-3 (5):
| Edge | Weight | Ends already connected? | Take it? | Total |
|---|---|---|---|---|
| 0-1 | 1 | no | yes | 1 |
| 1-2 | 2 | no | yes | 3 |
| 0-2 | 3 | yes, through 1 | no (a cycle) | 3 |
| 2-3 | 4 | no | yes; 3 edges, stop | 7 |
Prim's grows a tree from node 0 instead, always adding the cheapest edge that leaves it, and takes the same three edges here.
Java
// Kruskal's: take edges cheapest-first, skipping any that would close a cycle
int kruskalMST(int n, int[][] edges) { // edges: {u, v, w}
Arrays.sort(edges, (a, b) -> Integer.compare(a[2], b[2]));
int[] parent = new int[n];
for (int i = 0; i < n; i++) parent[i] = i;
int total = 0, used = 0;
for (int[] e : edges) {
int ru = find(parent, e[0]), rv = find(parent, e[1]);
if (ru != rv) { // different components: this edge is safe
parent[ru] = rv;
total += e[2];
if (++used == n - 1) break;
}
}
return total;
}
int find(int[] parent, int x) {
while (parent[x] != x) x = parent[x] = parent[parent[x]]; // path halving keeps trees shallow
return x;
}
// Prim's: grow one tree, always adding the cheapest edge leaving it
int primMST(int n, List<List<int[]>> adj) { // adj.get(u) holds {v, w}
boolean[] inTree = new boolean[n];
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> Integer.compare(a[1], b[1])); // {node, edge weight}
pq.add(new int[]{0, 0});
int total = 0, added = 0;
while (!pq.isEmpty() && added < n) {
int[] cur = pq.poll();
if (inTree[cur[0]]) continue; // an older, pricier way in - already connected
inTree[cur[0]] = true;
total += cur[1];
added++;
for (int[] edge : adj.get(cur[0])) if (!inTree[edge[0]]) pq.add(edge);
}
return total;
}
Python
import heapq
# Kruskal's: take edges cheapest-first, skipping any that would close a cycle
def kruskal_mst(n: int, edges: list[list[int]]) -> int: # edges: [u, v, w]
edges.sort(key=lambda e: e[2])
parent = list(range(n))
total = used = 0
for u, v, w in edges:
ru, rv = find(parent, u), find(parent, v)
if ru != rv: # different components: this edge is safe
parent[ru] = rv
total += w
used += 1
if used == n - 1:
break
return total
def find(parent: list[int], x: int) -> int:
while parent[x] != x:
parent[x] = parent[parent[x]] # path halving keeps trees shallow
x = parent[x]
return x
# Prim's: grow one tree, always adding the cheapest edge leaving it
def prim_mst(n: int, adj: list[list[tuple[int, int]]]) -> int: # adj[u] holds (v, w)
in_tree = [False] * n
heap = [(0, 0)] # (edge weight, node)
total = added = 0
while heap and added < n:
w, node = heapq.heappop(heap)
if in_tree[node]:
continue # an older, pricier way in - already connected
in_tree[node] = True
total += w
added += 1
for nxt, weight in adj[node]:
if not in_tree[nxt]:
heapq.heappush(heap, (weight, nxt))
return total
Both rest on the cut property: the cheapest edge between any two groups of nodes belongs to some MST. Prim's groups are its tree and the rest; Kruskal's are the two components an edge joins.
A second flavor: dense graphs without a heap
On a complete graph, like points on a map, E is about V^2 / 2. Prim's with a plain array is O(V^2), which is optimal there:
Java
int[] key = new int[n]; // cheapest edge from the tree to each outside node
Arrays.fill(key, Integer.MAX_VALUE);
key[0] = 0;
for (int added = 0; added < n; added++) {
int u = -1;
for (int v = 0; v < n; v++) if (!inTree[v] && (u == -1 || key[v] < key[u])) u = v; // O(V) scan
inTree[u] = true;
total += key[u];
for (int v = 0; v < n; v++)
if (!inTree[v]) key[v] = Math.min(key[v], dist(u, v)); // min over the WHOLE tree
}
Python
key = [float("inf")] * n # cheapest edge from the tree to each outside node
key[0] = 0
for _ in range(n):
u = min((v for v in range(n) if not in_tree[v]), key=key.__getitem__) # O(V) scan
in_tree[u] = True
total += key[u]
for v in range(n):
if not in_tree[v]:
key[v] = min(key[v], dist(u, v)) # min over the WHOLE tree
key[v] must stay the minimum over the whole tree; overwriting it with dist(u, v) builds a greedy chain instead.
Where you'll see it
Network design (the least cable that reaches every site), clustering (cut the k - 1 most expensive MST edges for k clusters) and traveling-salesman approximations all start from an MST.
Which tool for which job?
| You need | Use |
|---|---|
| A list of edges | Kruskal's: sort, then union-find |
| A sparse graph in adjacency lists | Prim's with a heap |
| A dense or complete graph | Prim's with an array, O(V^2) |
| Short routes from a source | a shortest-path tree (Dijkstra), not an MST |
Common mistakes
| Mistake | What happens | Do this instead |
|---|---|---|
| Prim's without the in-tree skip | a node is counted twice (4 instead of 12) | skip popped nodes already in the tree |
| Union-find without either optimization | 4,999,950,000 parent hops instead of 199,997 | union by rank and path compression |
Overwriting key[v] in array Prim's | a greedy chain instead of a tree | keep the minimum over the whole tree |
| Assuming the graph is connected | a forest is returned silently | check that V - 1 edges were used |
Check yourself
Try to answer before opening each one - recalling beats re-reading.
1. Why do Kruskal's and Prim's both produce a minimum spanning tree, despite choosing edges so differently?
Show answer
Both take only the cheapest edge across some cut, and the cut property says that edge is always safe.
2. Why does Prim's skip a popped node that's already in the tree?
Show answer
A node is pushed once per edge that reaches it. Without the skip, a stale entry counts it again: on 0-1 (1), 0-2 (2), 1-2 (1), 2-3 (10), the total is 4 with node 3 left out, instead of 12.
3. Is the MST path between two nodes their shortest path?
Show answer
Not necessarily. In the triangle 0-1 (2), 1-2 (2), 0-2 (3), the MST's path from 0 to 2 costs 4, while the direct edge costs 3. The MST minimizes total weight, not routes.
Key takeaways
- The cut property - the cheapest edge across any cut is safe - justifies both algorithms.
- Kruskal's: sort edges, take each one that joins two union-find components.
- Prim's: grow one tree, skipping stale heap entries; on dense graphs use the O(V^2) array version.
- An MST is not a shortest-path tree.