↩ 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.
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 ten 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.