Minimum Spanning Trees: Kruskal and Prim
A minimum spanning tree connects all vertices with the least total edge weight. Kruskal sorts edges and uses union-find; Prim grows from a vertex with a heap. Both matched brute force on 300 graphs.
A minimum spanning tree of a connected, weighted, undirected graph is a set of V-1 edges that connects every vertex with the least total weight. Kruskal's algorithm adds the cheapest edge that does not close a cycle, using union-find; Prim's grows one tree with a min-heap. Interviewers expect both to run in O(E log V), justified by the cut property.
A minimum spanning tree (MST) of a connected, weighted, undirected graph is a set of V-1 edges that connects every vertex with the smallest possible total weight. Kruskal's algorithm adds the cheapest edge that does not close a cycle, Prim's grows one tree outward, and both run in O(E log V).
- A minimum spanning tree of a connected graph with V vertices has exactly V-1 edges; a disconnected graph gives a minimum spanning forest instead.
- The cut property: for any split of the vertices into two non-empty groups, the lightest edge crossing the split belongs to some minimum spanning tree.
- Kruskal's algorithm sorts edges and uses union-find for the cycle check, costing O(E log E), which equals O(E log V).
- Prim's algorithm runs in O(E log V) with a binary heap and in O(V squared) with an adjacency matrix and no heap, which wins on dense graphs.
- With tied edge weights the MST total is unique but the tree may not be: a 4-cycle with every edge of weight 1 has four MSTs, each of weight 3.
- Python implementations of Kruskal and Prim matched a brute-force checker on 300 of 300 random graphs and gave a total of 39 on the 7-vertex textbook graph.
01The problem: connect everything as cheaply as possible
You have seven offices and a price for laying cable between certain pairs. You want every office reachable from every other, and you want the cheapest total cable. Model offices as vertices and cable options as weighted undirected edges.
Any connected, cycle-free subset of edges that reaches every vertex is a spanning tree, and it always has exactly V-1 edges. Fewer edges would leave something disconnected; more would form a cycle, and you could drop the most expensive edge on that cycle. Of all spanning trees, the minimum spanning tree has the least total weight.
Two facts help in interviews. The MST total weight is unique even when ties exist, though the tree itself may not be. And the graph must be connected for a single MST to exist; on a disconnected graph you get a minimum spanning forest, one tree per component.
02Why a greedy choice is safe: the cut property
Both algorithms rest on one fact, the cut property. Split the vertices into any two non-empty groups. Look at the edges that cross between the groups. The lightest crossing edge belongs to some minimum spanning tree.
Sketch of why: suppose an MST leaves that edge out. Adding the edge to the tree creates a cycle, and that cycle must cross the split somewhere else, through another, equal or heavier edge. Swap that one out and you get a spanning tree that is no heavier. So choosing the lightest crossing edge never costs you.
Kruskal applies this repeatedly with the cut chosen implicitly by the current components. Prim applies it with the cut defined as the tree so far against everything else.
03Kruskal's algorithm: sort edges, skip cycles
Sort the edges from lightest to heaviest. Walk the list. For each edge, if its two endpoints are in different components, take the edge and merge the components; otherwise skip it, because it would close a cycle. Stop after V-1 edges.
The component test is the job of union-find (disjoint sets). With path compression and union by rank, each find or union is close to constant, so sorting dominates: O(E log E), which is the same as O(E log V) because E is at most V squared.
Kruskal works well on sparse graphs and when edges arrive as a list. It also handles disconnected graphs without changes, producing a forest.
04Prim's algorithm: grow one tree with a heap
Start with any vertex. Push all its edges onto a min-heap keyed by weight. Pop the cheapest edge. If its far end is already in the tree, discard it; otherwise add that vertex, add the edge weight to the total, and push the new vertex's edges. Repeat until all vertices are in.
Each edge enters the heap at most twice (once from each end), so the heap work is O(E log E) = O(E log V). The structure resembles Dijkstra's algorithm, but the key is the weight of a single edge into the tree rather than the total distance from the source. That difference is a classic wrong-answer trap.
Prim fits dense graphs and adjacency lists. With an adjacency matrix and no heap it is O(V squared), which beats the heap version when E is close to V squared.
05Both in Python, checked against brute force
This is the code I ran, with a small union-find, Kruskal, Prim, a worked example, and a brute-force checker that tries every set of V-1 edges.
import heapq, random, itertools
class DSU:
def __init__(self, n): self.p = list(range(n)); self.r = [0]*n
def find(self, x):
while self.p[x] != x:
self.p[x] = self.p[self.p[x]]; x = self.p[x]
return x
def union(self, a, b):
a, b = self.find(a), self.find(b)
if a == b: return False
if self.r[a] < self.r[b]: a, b = b, a
self.p[b] = a; self.r[a] += self.r[a] == self.r[b]
return True
def kruskal(n, edges): # edges: (w, u, v)
d, total, used = DSU(n), 0, []
for w, u, v in sorted(edges):
if d.union(u, v):
total += w; used.append((u, v, w))
return total, used
def prim(n, edges, start=0):
adj = [[] for _ in range(n)]
for w, u, v in edges:
adj[u].append((w, v)); adj[v].append((w, u))
seen, heap, total = {start}, list(adj[start]), 0
heapq.heapify(heap)
while heap and len(seen) < n:
w, v = heapq.heappop(heap)
if v in seen: continue
seen.add(v); total += w
for e in adj[v]:
if e[1] not in seen: heapq.heappush(heap, e)
return total
# worked example
E = [(7,0,1),(5,0,3),(8,1,2),(9,1,3),(7,1,4),(5,2,4),(15,3,4),(6,3,5),(8,4,5),(9,4,6),(11,5,6)]
print("kruskal:", kruskal(7, E))
print("prim :", prim(7, E))
# brute-force check on small random connected graphs
def brute(n, edges):
best = None
for combo in itertools.combinations(edges, n-1):
d = DSU(n)
if all(d.union(u, v) for _, u, v in combo):
s = sum(w for w, _, _ in combo)
best = s if best is None or s < best else best
return best
random.seed(7)
ok = 0; tests = 300
for _ in range(tests):
n = random.randint(3, 7)
edges = [(random.randint(1, 20), i, random.randrange(i)) for i in range(1, n)] # spanning tree backbone
for _ in range(random.randint(0, 6)):
u, v = random.sample(range(n), 2); edges.append((random.randint(1, 20), u, v))
b = brute(n, edges)
ok += kruskal(n, edges)[0] == prim(n, edges) == b
print(f"kruskal == prim == brute force on {ok}/{tests} random graphs")
# equal weights: MST weight is unique, the tree need not be
sq = [(1,0,1),(1,1,2),(1,2,3),(1,3,0)]
print("4-cycle all weight 1:", kruskal(4, sq))Output:
kruskal: (39, [(0, 3, 5), (2, 4, 5), (3, 5, 6), (0, 1, 7), (1, 4, 7), (4, 6, 9)])
prim : 39
kruskal == prim == brute force on 300/300 random graphs
4-cycle all weight 1: (3, [(0, 1, 1), (1, 2, 1), (2, 3, 1)])The worked example is the common seven-vertex textbook graph; the six chosen edges weigh 5+5+6+7+7+9 = 39. The random test used graphs of 3 to 7 vertices with a guaranteed spanning backbone, a fixed seed, and weights 1 to 20. The last line shows ties: a 4-cycle where every edge weighs 1 has four different MSTs, each weighing 3. Kruskal returns one of them depending on sort order, so do not assert an exact edge list in tests when weights tie.
06Choosing between them and common traps
Use Kruskal if you already have an edge list or the graph is sparse. Use Prim when the graph is stored as adjacency lists and is dense, or when you want to grow the tree incrementally. Complexities are the same order, so pick the one that makes the code shorter for your input.
Traps worth naming: negative weights are fine for MST, unlike Dijkstra. Directed graphs need a different algorithm (minimum arborescence, Chu-Liu/Edmonds), which I mention only so you know the answer is not Kruskal. Forgetting the connectivity check leaves you with a forest and a wrong claim of V-1 edges. Real uses include network and cable layout, clustering by cutting the heaviest MST edges, and approximation algorithms for travelling-salesman style problems.
07Common interview questions
Q: How many edges does an MST of V vertices have?
A: Exactly V-1, assuming the graph is connected.
Q: Is the MST unique?
A: If all edge weights are distinct, yes. With ties the total weight is unique but several trees can achieve it.
Q: Why does Kruskal need union-find?
A: To test in near-constant time whether an edge's endpoints are already connected, which is the cycle check.
Q: Time complexity of Kruskal and of Prim?
A: Kruskal O(E log E), equal to O(E log V). Prim O(E log V) with a binary heap, O(V squared) with a matrix and no heap.
Q: How does Prim differ from Dijkstra?
A: Prim's key is the weight of one edge into the tree; Dijkstra's key is the total path length from the source.
Q: State the cut property.
A: For any partition of the vertices, the lightest edge crossing it is in some MST.