↩ back to Minimum Spanning Trees
Prim's algorithm builds the same thing Kruskal's algorithm does — a minimum spanning tree — but grows it the opposite way. Kruskal looks at the whole edge list at once, globally sorted, and decides edge-by-edge whether each one belongs. Prim never looks at the whole list: it starts from a single node, keeps a "frontier" of the cheapest known edge from the current tree to every node not yet in it, and at each step reaches out along whichever frontier edge is cheapest right now. One tree grows outward from a seed, one node at a time, instead of one global sort deciding everything up front. A third approach, Borůvka's algorithm, is neither: every component grows outward from itself at once, in simultaneous rounds, rather than one seed or one sorted pass.
The exact same seven-waypoint trail network Kruskal's algorithm uses — same nodes, same edge costs — so the two pages are directly comparable. Press Step or Run: the tree starts at Basecamp (filled in) and grows outward. Each step either adds a node — its connecting edge turns solid orange, the node fills in — or pops a stale candidate from the priority queue below the graph (an edge to a node that already joined the tree by a cheaper route in the meantime, popped and discarded rather than acted on). The priority queue is shown as a chip strip, cheapest candidate first; a dashed edge in the graph is a candidate still waiting in the queue, not yet accepted or discarded.
Prim's algorithm leans on the exact same cut property Kruskal's does: for any split of the graph's nodes into two non-empty groups, the cheapest edge crossing that split must belong to some minimum spanning tree. Prim just picks a specific, ever-growing split to exploit it with — "nodes already in the tree" versus "everything else." At every step, the cheapest edge leaving the tree side of that split is safe to add, by the cut property, and adding it grows the tree side by exactly one node, which defines a new split for the next step. Kruskal proves the same property holds edge-by-edge in global sorted order; Prim proves it one cut at a time, always the cut between "what's in the tree so far" and "what isn't." Different bookkeeping, same guarantee, so on a graph with no tied edge weights — like the demo's trail network — the two algorithms are guaranteed to find the identical minimum spanning tree, just by walking to it in a different order.
An array-backed priority queue holding candidate (weight, node, via) triples, same
lazy-deletion approach Dijkstra's algorithm uses: a node can
be pushed more than once if a cheaper connecting edge turns up later, and the stale, more expensive
copy is just popped and skipped once it's no longer the best way in.
function primMST(numNodes, edges, start) {
const adj = Array.from({ length: numNodes }, () => []);
edges.forEach(({ a, b, w }) => {
adj[a].push({ to: b, w });
adj[b].push({ to: a, w });
});
const inTree = new Array(numNodes).fill(false);
let pq = [[0, start, -1]]; // [weight, node, viaNode]
const mst = [];
let totalWeight = 0;
while (pq.length) {
pq.sort((x, y) => x[0] - y[0]);
const [w, node, via] = pq.shift();
if (inTree[node]) continue; // stale candidate — a cheaper edge already won
inTree[node] = true;
if (via !== -1) {
mst.push({ a: via, b: node, w });
totalWeight += w;
}
for (const { to, w: edgeWeight } of adj[node]) {
if (!inTree[to]) pq.push([edgeWeight, to, node]);
}
}
return { mst, totalWeight, reached: inTree.filter(Boolean).length };
}
A real implementation swaps the linear pq.sort()/pq.shift() pair for a
binary heap, same upgrade Dijkstra's algorithm names in its
own Pitfalls section — see Complexity below for what that upgrade actually buys.
Prim only ever sees the component it starts in. If the graph is disconnected,
Prim's frontier runs dry — every remaining node is unreachable from anything already in the tree —
and the algorithm just stops, having built the minimum spanning tree of only the piece
containing the start node. It has no way to notice the rest of the graph exists, let alone
report it. That's a real difference from Kruskal's algorithm,
which processes every edge regardless of which component it's in and so naturally produces a
spanning forest covering every piece; Prim would need to be restarted from a fresh node in each
undiscovered component to do the same. Worth checking reached === numNodes if a single
connected tree was assumed.
Ties mean the tree isn't always unique — same caveat Kruskal's algorithm makes. If two candidate edges in the priority queue share the same weight, which one sorts first can change which edges end up in the tree, though never the total weight. The demo's ten trail costs are all distinct so there's exactly one right answer to point at.
The starting node never changes which tree you get (weights permitting) — only the order nodes join in. Every node the tree could reach, it reaches regardless of where it starts, and the cut-property argument above holds from any starting node. Pick a different start on this same graph and the algorithm still ends at the identical six edges, total weight 22 — just discovered in a different sequence.
A stale priority-queue entry looks like wasted work but isn't a correctness bug. Same story as Dijkstra's algorithm's priority queue: pushing a second, cheaper candidate for a node already sitting in the queue is simpler than trying to find and update the old entry in place, and popping the stale one later costs a cheap skip, not a wrong answer.
The Pitfall above calls a stale pop "wasted work" with no number attached. The Try it demo's
own graph already has one, countable by hand from the trace above: 10 edges, 7 nodes, 4 stale pops
before the tree finishes. That's not a coincidence of this particular graph — it falls out of
exactly how lazy deletion pushes candidates. Walk the push side of the loop: an edge (u,
v) only ever gets pushed once, from whichever of u/v is accepted
first (the check is "is the other endpoint still outside the tree?" — once either
side is accepted, the other side's own turn can never trigger a second push for the same edge,
because by then the first side already is in the tree). So every edge contributes exactly one push
over the whole run, plus the one push that bootstraps the start node, for E + 1 pushes
total. Every push eventually gets popped — nothing else removes a candidate — and exactly
V of those pops are real (one per node reached, each only ever accepted once). That
pins the stale count exactly:
stale pops = E − V + 1
On the demo's own graph: 10 − 7 + 1 = 4, matching the trace exactly. That
quantity has a name — it's the graph's circuit rank, the count of edges left over
once a spanning tree's V − 1 are accounted for, i.e. exactly how many independent
cycles the graph has. Every edge beyond what bare connectivity requires produces exactly one
discarded candidate, no more, no less, regardless of edge weights, tie-breaking, or which node Prim
starts from.
Each click builds a genuinely new random graph — different weights, different shape, real
Math.random(), not the fixed seed this site's other races use to keep their prose
numbers reproducible run to run. The point here isn't one number, it's that the formula holds
exactly every time, not just on average — press it repeatedly and the measured stale count
always matches E − V + 1, never off by one in either direction. At avg. degree 4
(twice the V − 1 a spanning tree needs) roughly half of every pop measured while
writing this page was stale; at 16, about 87.5%; at 64, nearly
97%. Density is what drives the waste, not graph size — the real work stays fixed
at exactly V pops no matter how large the graph gets, while the circuit rank, and so
the stale count, grows with every edge added beyond a spanning tree.
Time: O(E log V) with a binary-heap priority queue — every edge can
trigger one push, and each push/pop costs O(log V). The reference implementation above
uses a linear-scan array instead (matching the demo), which costs O(E · V) in the worst
case — the same array-vs-heap tradeoff Dijkstra's algorithm
makes, for the same reason: simplicity of the code shown, not simplicity of the real cost.
Space: O(V + E) — the adjacency list is O(E), the
priority queue holds at most one entry per edge in the worst case, also O(E), plus
O(V) for the in-tree marks.
For a decision guide across all twelve of this site's Minimum Spanning Trees entries — when to reach for Prim's over Kruskal's or Borůvka's, and when the real question is bottleneck or second-best instead of minimum total — see Choosing a Minimum Spanning Tree Algorithm.