Don't memorize Prim's algorithm — watch the tree grow. A minimum spanning tree connects every vertex for the least total weight. Prim grows one tree outward from a starting vertex: each step it looks at every edge crossing from the tree to the outside and greedily grabs the cheapest, pulling one new vertex in. A min-heap keeps that cheapest edge at your fingertips, and the cut property proves the greedy grab is always safe.
grow from one vertex · cheapest crossing edge · min-heap frontier · cut property
MST
A tree touching every vertex with minimum total weight — exactly V − 1 edges, no cycle.
CROSSING EDGE
An edge with one endpoint in the growing tree and one outside it.
GREEDY GROW
Always add the cheapest crossing edge — the cut property says it is safe.
MIN-HEAP
A priority queue of frontier edges hands you the cheapest in O(log V).
prim.sim — grow the MST from vertex A
Ready
A weighted graph. Start with just A in the tree. Press Step: the blue dashed edges are the current frontier — the cheapest one (amber) gets added, turns green, and pulls in a new vertex.
repeat: add the min-weight edge crossing tree → outside
0
MST weight
1 / 5
Vertices in tree
The cut property does the proving
Why is grabbing the locally cheapest edge safe? Because of the cut property. Split the vertices into two groups — say the tree so far versus everything else. Any spanning tree must cross that divide somewhere. And the cheapest edge crossing it can always be part of a minimum spanning tree: if some MST used a pricier crossing edge instead, you could swap in the cheaper one and get a tree that is no heavier. Prim leans on this every step. Its cut is always the same shape — the vertices already in the tree versus the rest — and it adds the least-weight edge across that cut. One new vertex joins, the cut redraws itself, and you repeat. A min-heap of the frontier edges makes each cheapest lookup O(log V).
01
Start anywhere
Put a single vertex in the tree. Any starting vertex yields a minimum spanning tree.
02
Look at the cut
Consider every edge crossing from the in-tree vertices to the vertices still outside.
03
Add the cheapest
Take the minimum-weight crossing edge; the cut property makes it safe. One new vertex joins.
04
Repeat V − 1 times
A min-heap keyed by edge weight yields each pick in O(log V), for O((V + E) log V) total.
Time
O((V+E) log V)
Space
O(V)
Edges
V − 1
Proof
Cut property
Prim and Kruskal are the two classic MST builders, and both are greedy. Prim grows a single connected tree outward with a heap of frontier edges — a great fit for dense graphs. Kruskal instead sorts all edges once and adds them cheapest-first, using union-find to reject any that would close a cycle — better for sparse graphs. Prim also looks almost identical to Dijkstra: same heap-driven loop, except Dijkstra keys by distance from the source while Prim keys by the single edge into the tree. Learn one and the other two come nearly free.
Check yourself
1 · What does Prim add at each step?
Prim only considers frontier edges — those leaving the current tree — and takes the minimum-weight one, bringing in one new vertex.
2 · Why is the greedy choice guaranteed correct?
For the cut between the tree and the rest, the cheapest crossing edge can always belong to a minimum spanning tree — so adding it never rules out optimality.
3 · How does Prim differ from Kruskal?
Both build a minimum spanning tree. Prim expands one connected tree; Kruskal processes edges globally cheapest-first, skipping cycles with union-find. Same total weight.
Questions
Prim or Kruskal — which should I use?
Both give a minimum spanning tree. Prim with a heap is O(E log V) and shines on dense graphs (and can be O(V²) with a simple array). Kruskal is O(E log E) dominated by sorting the edges plus near-constant union-find, which suits sparse graphs. Pick by graph density.
Does the MST depend on the start vertex?
No. Prim produces a minimum spanning tree from any starting vertex. If all edge weights are distinct the MST is unique, so the start cannot change it; with tied weights you might get a different edge set but the same total weight.
Why does Prim look so much like Dijkstra?
Both run a heap-driven greedy loop that repeatedly extracts the closest outside vertex. The only difference is the key: Dijkstra uses the total distance from the source, while Prim uses just the weight of the single edge connecting a vertex to the current tree.
One tree, always the cheapest way out.
Start with a vertex, add the least-weight crossing edge, redraw the cut, repeat. The cut property makes every greedy step safe.