Connect every vertex using the least total edge weight. Kruskal sorts edges globally; Prim grows outward from one node. Both are greedy, both are optimal — and they often pick different edges.
Controls
Edges by weight
Building the Tree
step 0
Insight
An MST connects all V vertices with exactly V−1 edges and no cycles, at minimum total weight.
edges chosen0
needed–
total weight0
rejected0
Complexity
KruskalO(E log E)
Prim (heap)O(E log V)
SpaceO(V+E)
Minimum Spanning Tree
Two greedy algorithms, two different routes, the same minimum total.
Quick Context
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.
Interactive Exploration Guide
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.
Key Takeaway
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.
Cheat sheet
Minimum Spanning Tree
Connect every vertex using the least total edge weight. Kruskal sorts edges globally; Prim grows outward from one node. Both are greedy, both are optimal — and they often pick different edges.