Minimum Spanning Trees: Kruskal and Prim
Imagine laying fibre between offices or running power to a set of villages. You need everything connected and you want to spend as little as possible.
The result is called a minimum spanning tree. Spanning because it touches every node, tree because it has no cycles, minimum because it is the cheapest spanning tree.
Why the answer is a tree
Suppose your solution contains a cycle. Then you can delete any one edge of that cycle and everything stays connected, because the rest of the cycle still joins the two ends. You just made it cheaper without losing anything. So a cheapest solution never contains a cycle, assuming there are no negative weights.
Connected and acyclic is exactly the definition of a tree, and we know that a tree of n nodes has exactly n - 1 edges. You know in advance how many edges your answer contains, which gives you a clean place to stop.
How and why a greedy solution works
Greedy algorithms usually deserve further analysis. Sometimes greedy algorithms miss better solutions where the value just wasn't notice immediately. So it is fair to be sceptical of a plan that says "keep taking the cheapest edge you can".
Consider splitting the nodes into any two groups. Call an edge a "crossing edge" if it connects nodes in different groups. The cheapest crossing edge is always safe, meaning some minimum spanning tree contains it.
To prove the argument in orange, we can use contradiction. Consider a spanning tree that doesn't use the cheapest crossing edge e , instead using some other crossing edge e' . Adding e to the spanning tree creates a cycle because the two endpoints were already connected through another path using e' . Because it's a cycle, we can remove the edge e' and still have all nodes connected. Thus, there always exists a minimum spanning tree containing the cheapest crossing edge.
In this problem, there are local "decisions" that are never wrong. In shortest paths there is not, which is why Dijkstra needs its more careful argument about settling the smallest tentative distance.
Kruskal's algorithm
If cheap edges are safe, the simplest possible plan is to sort every edge by cost and take them in order, skipping any that would close a cycle.
Sorting the edges once and testing each against a cycle check is the whole algorithm. The only real work is answering "would this edge close a cycle?" quickly, which the next section covers. Below is the exact graph this page's numbers use: step through it in Kruskal mode and match each take or skip against the running total.
Kruskal ignores where the edges are on the page and just sorts them cheapest first. Right now every node is its own island.
Edges, cheapest first
A spanning tree over 5 nodes always uses exactly 4 edges, so the run stops the moment it has them.
Notice B-C and B-D being skipped. They are rejected purely because their endpoints had already been joined by earlier choices, and adding them would have created a loop for no gain.
Prim's algorithm, the other way round
There is a second approach that is just as valid but has a different use case.
Kruskal grows many small fragments all over the graph and eventually merges them, while Prim grows a path outward from a starting node. Each step of Prim's algorithm iterates through all the edges outward and taking the node on the end of the cheapest edge.
That is the safe-edge property applied with the two groups being "in my blob" and "everything else". Both algorithms are the same theorem used differently, which is why they always produce a tree of the same total cost even when they pick different edges to get there.
| Kruskal | Prim | |
|---|---|---|
| Grows | Many fragments that merge | One blob from a start node |
| Needs | All edges sorted, plus union-find | A heap of edges leaving the blob |
| Cost | O(E log E), dominated by the sort | O(E log V) with a binary heap |
| Suits | Sparse graphs, or edges already sorted | Dense graphs |
| Input it likes | A flat edge list | An adjacency list |
Watch both run
Switch between the two on the same graph you just watched Kruskal solve above. The final total is always identical. What differs is the order the edges get chosen in, and which ones a partial run has already committed to.
Kruskal ignores where the edges are on the page and just sorts them cheapest first. Right now every node is its own island.
Edges, cheapest first
A spanning tree over 9 nodes always uses exactly 8 edges, so the run stops the moment it has them.
Don't forget that there can exist multiple minimum spanning trees.
The implementation
function kruskal(nodeCount, edges) {
const parent = Array.from({ length: nodeCount }, (_, i) => i);
function find(x) { // which group is x in?
while (parent[x] !== x) {
parent[x] = parent[parent[x]]; // flatten as we walk
x = parent[x];
}
return x;
}
function union(a, b) { // merge two groups
const ra = find(a), rb = find(b);
if (ra === rb) return false; // already together, this edge is a cycle
parent[ra] = rb;
return true;
}
const sorted = [...edges].sort((x, y) => x.weight - y.weight);
const tree = [];
for (const edge of sorted) {
if (union(edge.from, edge.to)) tree.push(edge);
if (tree.length === nodeCount - 1) break; // a tree is full
}
return tree;
}Where it goes wrong
Running it on a disconnected graph. If the graph comes in separate pieces there is no spanning tree at all, and Kruskal will quietly return a forest with fewer than n - 1 edges. Check the count before trusting the result.
Using it for shortest paths. A minimum spanning tree minimizes total cost across the whole network. It does not minimize the distance between any particular pair, and the route between two nodes in an MST is often far from their shortest path. Different question, different algorithm.
Skipping path compression in union-find. It still works and it gets slow, because the chains grow long on large inputs. The one extra line is worth writing every time.
Assuming negative weights are a problem. They are not, here. Nothing in the safe-edge argument assumed weights were positive, so both algorithms handle negative edges without modification. That is a real difference from Dijkstra, and it is worth noticing why: this argument never needed "adding edges cannot make things cheaper".
Check yourself
Why can a minimum spanning tree never contain a cycle?