Minimum Spanning Tree: Kruskal & Prim

Connect every town with cable, every office with fibre, every island with a bridge, at the lowest total cost. Two short greedy algorithms solve it exactly, and you already know both of their engines: Union-Find and Dijkstra.

advanced⏱ 14 min read

←Builds on

8Union-Find (DSU)Kruskal asks "same component?" for every edge, which is DSU's find.8Dijkstra's AlgorithmPrim is Dijkstra with a different key: the cheapest edge into the tree, not the total distance.7The Greedy Idea & When It FailsBoth Kruskal and Prim are greedy: always add the cheapest safe edge.

Leads to→

12P vs NP & Choosing an AlgorithmAn MST gives a tour at most twice the optimum for metric TSP, a classic way to cope with hardness.

1Learn 2Play 3Check 4Practice

Learn

The idea, the mechanics and the cost.

01Spanning tree, minimum total weight

Take a connected, undirected, weighted graph. A spanning tree is a set of edges that connects all V vertices and contains no cycle; it always has exactly V − 1 edges. A minimum spanning tree (MST) is one whose total weight is as small as possible.

Note the difference from shortest paths: the MST minimizes the sum of all chosen edges, not the distance from one source. The route between two vertices inside an MST can be long; what is cheap is the network as a whole.

For the 7-vertex graph of the visualizer the MST uses 6 edges with total weight 39. There can be several MSTs with the same total when weights repeat, but the minimum total is unique.

02Why greedy works here: the cut property

Split the vertices into any two sides; the edges between the sides cross the cut. The cut property: the lightest crossing edge belongs to some minimum spanning tree.

The proof is an exchange argument, just like activity selection in stage 7. Take an MST without that edge e. Adding e creates a cycle, and that cycle must cross the cut a second time through some edge f. Since w(e) ≤ w(f), swapping f for e gives a spanning tree that is no heavier.

So it is always safe to add the lightest edge across a cut. Both classic algorithms are just two ways of choosing which cut to look at.

03Kruskal: sort the edges, skip cycles with DSU

Kruskal's algorithm looks at edges from lightest to heaviest:

sort all edges by weight;
for each edge (u, v): if find(u) != find(v), take it and union(u, v); otherwise it would close a cycle, so skip it;
stop after V − 1 edges.

Each accepted edge is the lightest edge across the cut "u's component vs. the rest", so the cut property makes it safe. The DSU from the previous topic answers the cycle question in near O(1).

On our graph: 1-4 (5) ✓, 3-5 (5) ✓, 4-6 (6) ✓, 1-2 (7) ✓, 2-5 (7) ✓, then 2-3, 5-6 and 2-4 are skipped, and 5-7 (9) completes the tree: 39. Total cost O(E log E), dominated by the sort.

04Prim: Dijkstra with a different key

Prim's algorithm grows one tree from a start vertex. At every step it adds the lightest edge from the tree to a vertex outside it: the cut is "tree vs. rest".

In code it is Dijkstra almost line for line: a min-heap, pop the smallest, mark it, update the neighbours, skip outdated pairs. The only change is the key:

Dijkstra: d[v] = d[u] + w, the whole distance from the source;
Prim: key[v] = w, just the one edge that would attach v to the tree.

With a binary heap Prim costs O(E log V). Kruskal is simpler when you already have an edge list; Prim suits dense graphs or adjacency lists. Either one finds weight 39 here, from any start vertex.

Cost at a glance

Kruskal (sort + DSU)O(E log E)

Prim with a binary heapO(E log V)

Prim on a dense graph, array scanO(V²)

Remember

A minimum spanning tree connects all V vertices with V − 1 edges of least total weight.
The cut property makes greedy safe: the lightest edge across any cut belongs to some MST.
Kruskal = sorted edges + DSU cycle check; Prim = Dijkstra whose key is a single edge weight.

Play

Step through the algorithm, then try it on your own input.

👀 What to watch: In the Kruskal phase, watch rejected edges: both ends are already in one component. In the Prim phase, try another start vertex: the total is still 39.

Interactive visualizerfocus here, then space ← →

Kruskal: sorted edges · total weight: 0

Kruskal: sorted edges

1-4 (5)3-5 (5)4-6 (6)1-2 (7)2-5 (7)2-3 (8)5-6 (8)2-4 (9)5-7 (9)6-7 (11)4-5 (15)

A spanning tree connects all vertices with no cycles; the MINIMUM one has least total weight. Kruskal sorts every edge by weight and adds the cheapest that stays acyclic.

Pseudocode

 1 Kruskal: sort edges ascending by weight 2   for each edge (u,v): if u,v in different sets (DSU) 3     accept it and union; else it would form a cycle → reject 4   stop after V-1 edges 5 Prim: grow a tree from one vertex, 6   repeatedly add the lightest edge crossing the cut

1 / 1

Check

Three questions. Pick an answer to see why.

A connected graph has 10 vertices and 25 edges. How many edges does its minimum spanning tree have?

Kruskal reaches edge 2-3 (weight 8), and find(2) == find(3). What happens?

Prim pops vertex u and looks at edge (u, v, w) with v outside the tree. How does it update v?

Practice

Real problems to lock it in, easiest first.

LeetCodeMin Cost to Connect All Points intermediate↗CSESRoad Reparation intermediate↗LeetCodeFind Critical and Pseudo-Critical Edges in Minimum Spanning Tree advanced↗