Start here
A spanning tree connects every vertex of a graph using exactly V−1 edges and no cycles. The minimum spanning tree is the one with the smallest total edge weight — the cheapest way to keep everything connected.
Kruskal: Sort Globally, Add Safely
- Sort every edge by weight, cheapest first.
- Take each in turn. Add it if its endpoints are in different components; skip it if they are already connected, since that would create a cycle.
- Stop after V−1 edges.
The connectivity check is exactly what union-find is for — a near-constant-time "same group?" query. Kruskal is the headline application of that structure.
Notice that Kruskal's partial result is often a forest of disconnected fragments that only merge into one tree at the end.
Prim: Grow One Tree Outward
- Start at any vertex.
- Repeatedly add the cheapest edge that connects the tree to a vertex not yet in it.
- Stop when every vertex is included.
Prim keeps a single connected tree at all times, which is why it needs a priority queue of frontier edges rather than union-find. With a binary heap it runs in O(E log V).
Why Greedy Is Provably Correct Here: The Cut Property
Split the vertices into any two groups. The cheapest edge crossing that divide must be in some MST. That is the cut property, and both algorithms are just different ways of applying it.
Prim applies it to the cut between "in the tree" and "not in the tree". Kruskal applies it implicitly — when it adds the cheapest edge joining two components, that edge crosses the cut between them.
This is why greedy never has to backtrack, unlike the coin-change failure in the greedy module.
Which One to Use
- Kruskal suits sparse graphs — the cost is dominated by sorting E edges. It also works naturally when edges arrive as a list.
- Prim suits dense graphs, where E approaches V², because it never sorts everything.
If edge weights are all distinct the MST is unique, so both produce identical trees. With ties they may choose different edges — but the total weight always matches.
Real Uses
Laying cable, pipe or road networks at minimum cost; clustering (remove the k−1 most expensive MST edges to get k clusters); approximation algorithms for the travelling salesman problem; and network design generally.
The cheapest way to connect everything
Given a weighted undirected graph, a spanning tree connects all vertices using exactly V−1 edges and no cycles. A minimum spanning tree is the one with the lowest total weight.
The practical question it answers: what is the cheapest set of connections that leaves nothing isolated? Laying cable, building a road network, connecting offices — wherever connectivity is required and redundancy is not.
Two properties are worth stating, because they are what the algorithms rely on:
Exactly V−1 edges. Fewer leaves the graph disconnected; more creates a cycle, and the heaviest edge in a cycle can always be removed.
The cut property. For any way of splitting the vertices into two groups, the lightest edge crossing the split is in some MST. That single fact is what makes greedy algorithms correct here.
The MST is not necessarily unique — equal edge weights allow several — but the total weight is.
Kruskal's algorithm
Sort every edge by weight and add each one unless it would create a cycle.
def kruskal(n, edges):
uf = UnionFind(n)
mst, total = [], 0
for weight, u, v in sorted(edges):
if uf.union(u, v): # False if u and v are already connected
mst.append((u, v, weight))
total += weight
if len(mst) == n - 1:
break # done
return mst, total
The cycle check is the Union-Find union returning False. If both endpoints already share a component, adding the edge would close a cycle.
O(E log E) for the sort, plus effectively O(E) for the union operations — so sorting dominates. The algorithm builds a forest that gradually merges into one tree, which is why it does not care whether the graph is connected until the end.
Prim's algorithm
Grow a single tree from an arbitrary starting vertex, repeatedly adding the cheapest edge that reaches a new vertex.
import heapq
def prim(graph, start):
visited = {start}
pq = [(w, start, v) for v, w in graph[start]]
heapq.heapify(pq)
mst, total = [], 0
while pq and len(visited) < len(graph):
w, u, v = heapq.heappop(pq)
if v in visited:
continue # stale entry
visited.add(v)
mst.append((u, v, w))
total += w
for nxt, weight in graph[v]:
if nxt not in visited:
heapq.heappush(pq, (weight, v, nxt))
return mst, total
Structurally this is Dijkstra's algorithm with one change: the priority is the edge weight rather than the accumulated distance from the source. Dijkstra asks "how far from the start?"; Prim asks "how cheap to attach?"
| | Kruskal | Prim |
|---|
| Grows | A forest, merging | One tree |
| Needs | Sorted edges, Union-Find | A priority queue |
| Complexity | O(E log E) | O(E log V) with a heap |
| Better on | Sparse graphs | Dense graphs |
| Disconnected graphs | Produces a forest naturally | Needs restarting per component |
For dense graphs, Prim with an adjacency matrix and a linear scan is O(V²), which beats the heap version when E approaches V².
Two algorithms, one answer, and the property that guarantees it
Kruskal and Prim look nothing alike -- one sorts all the edges globally, the other grows a single tree outward -- and they return trees of the same total weight every time. That is not a coincidence, and the cut property is what makes it inevitable.
Things to try
- Run Kruskal. Watch it consider edges in weight order and reject any that would close a cycle.
- Note the disconnected fragments mid-run — Kruskal builds a forest that only becomes one tree at the very end.
- Switch to Prim on the same graph. The tree stays connected throughout, growing outward from a single vertex.
- Compare the final totals. They match exactly, even when the chosen edges differ.
- Count the edges: always V−1. One fewer than the number of vertices — that is what makes it a tree.
Worth remembering
An MST connects everything with V−1 edges at minimum cost. Kruskal sorts all edges and uses union-find to reject cycles; Prim grows one tree using a priority queue. The cut property proves both greedy strategies optimal, so neither ever needs to reconsider.
Where MSTs are used
- Network design. Laying fibre, power lines or pipes to connect sites at minimum cost — the original motivating problem.
- Clustering. Build the MST, then remove the k−1 heaviest edges to get k clusters. This is single-linkage hierarchical clustering, and the MST is exactly what it computes.
- Image segmentation. Pixels as vertices, colour difference as weight; the MST's structure reveals regions.
- Approximation algorithms. A traveling-salesman tour built by walking the MST is within a factor of 2 of optimal, and Christofides' refinement gets to 1.5.
- Circuit and layout design for minimum wire length.
- Maze generation. A random spanning tree of a grid is a maze with exactly one path between any two cells.
The clustering use is the one most likely to be encountered outside a networking context, and the connection is worth remembering: MST plus cutting the heaviest edges is single-linkage clustering.
MST against shortest paths
A common confusion, and the distinction is sharp.
An MST minimises the total weight of the whole tree. It says nothing about the distance between any particular pair.
A shortest-path tree minimises the distance from one source to every vertex. Its total weight is generally larger than the MST's.
Concretely, in a triangle with edges A—B = 1, B—C = 1, A—C = 3: the MST is {A—B, B—C} with total 2. The shortest path from A to C in that tree is 2, which happens to match the true shortest path — but in general the path between two vertices within the MST can be much longer than their shortest path in the graph.
So: use an MST when you need cheap global connectivity; use Dijkstra when you need distances.
Maximum spanning tree. Negate the weights and run the same algorithm. Used in some clustering and network-reliability problems.
Bottleneck spanning tree. Minimise the heaviest edge rather than the total. The MST already achieves this — every MST is a minimum bottleneck spanning tree.
Steiner tree. Connect a subset of vertices, allowed to use others as intermediate points. NP-hard, unlike MST, and MST-based heuristics are the standard approach.
Minimum spanning forest. On a disconnected graph, Kruskal's produces one tree per component naturally.
Second-best MST. Found by trying, for each MST edge, the best replacement — useful for redundancy planning.
Borůvka's algorithm. The third classical MST algorithm, which adds the cheapest edge leaving every component simultaneously. It is the one that parallelises well, and it is the basis of modern distributed MST algorithms.
Questions people ask
Kruskal or Prim? Kruskal for sparse graphs and when the edges are already sorted or arriving as a list. Prim for dense graphs, especially with an adjacency matrix.
Is the MST unique? Not when edge weights tie. The total weight is unique; the edge set may not be.
Does it work with negative weights? Yes — unlike shortest-path algorithms, MST algorithms are unaffected by negative weights, because there is no notion of accumulating a path.
Does it give shortest paths? No. That is a different tree, computed by Dijkstra.
What if the graph is disconnected? Kruskal's produces a spanning forest. Prim's must be restarted from each unvisited vertex.
Why does greedy work here? The cut property: the lightest edge crossing any partition belongs to some MST, so taking it can never be a mistake.
Recap in one screen
- The cheapest V−1 edges that connect every vertex without a cycle.
- Kruskal sorts all edges and adds those that do not close a cycle, using Union-Find for the check.
- Prim grows one tree with a priority queue — Dijkstra with edge weight instead of path distance.
- Greedy is provably correct here because of the cut property.
- MST minimises the total; it does not give shortest paths — and cutting its heaviest edges gives single-linkage clusters.