Prim

The problem it solves

The same problem as Kruskal — connect every node for the cheapest total edge weight — solved with the opposite temperament. Where Kruskal audits a global price list and lets tree fragments fuse wherever they may, Prim grows one connected blob from a starting node, and at every step swallows the cheapest node it can reach: among all edges with one end inside the tree and one end outside, take the lightest, forever, until nothing is left outside.

Prim earns its separate page for two reasons. Practically, it is the MST algorithm of choice when the graph lives as adjacency lists and is dense — O(E log V) with a binary heap, O(E + V log V) with a Fibonacci heap, and O(V²) with a plain array, which on complete graphs beats every heap. Pedagogically, it is one character away from Dijkstra: the identical greedy loop — pop the best frontier entry, expand, push neighbours — with the heap keyed on edge weight instead of accumulated path cost. Seeing that one-key difference flip the problem from shortest-paths to cheapest-connectivity is one of the sharpest lessons the whole catalogue offers, and interviewers reach for it constantly.

The intuition — and where it breaks down

Picture the tree as a lit region spreading through a dark graph. The boundary — edges with exactly one lit endpoint — is the only place growth can happen, and Prim’s entire policy is: extend the light along the cheapest boundary edge. Why is that safe? Because of the cut property: for the cut between lit and unlit nodes, the lightest crossing edge belongs to some minimum spanning tree. Prim takes precisely that edge every time, so every acceptance is individually justified, and no acceptance is ever regretted or undone.

The mechanism that makes “cheapest boundary edge” cheap to find is the heap, and it comes with the same wrinkle Dijkstra has: entries go stale. An edge pushed when its far end was dark may be popped after that node has already been swallowed via a cheaper route. The lazy-deletion idiom handles it — pop, notice both ends are lit, discard, continue — and the player narrates these rejections explicitly, because they confuse everyone the first time: nothing is wrong; the heap is just serving yesterday’s news.

Where the intuition breaks: the blob picture suggests the nodes are what is being priced, but the heap holds edges (or equivalently, nodes keyed by their cheapest known crossing edge). Muddling “cost of the node” with “cost of the path to the node” is precisely the Dijkstra confusion — in Prim, history does not accumulate. A node three hops deep joins for the price of its one crossing edge, not the sum along the way. Watch the counters: tree weight grows by exactly the accepted edge’s weight, never by a path total.

Loading…

A walkthrough you can check

Nodes {A, B, C, D}, edges AB=1, AC=4, BC=3, BD=5, CD=2. Start at A.

1. Boundary of {A}: AB=1, AC=4. Take AB — B joins for 1. Push B’s edges: BC=3, BD=5.
2. Boundary of {A,B}: AC=4, BC=3, BD=5. Take BC — C joins for 3. Push CD=2.
3. Boundary of {A,B,C}: CD=2, BD=5, and AC=4 — but AC is now stale, both ends lit; when popped it is discarded. Take CD — D joins for 2.

Tree: AB + BC + CD = 6, matching Kruskal’s answer on the same graph (their acceptance orders differ; the total cannot). The step to internalise is 3: AC sat in the heap looking respectable at weight 4, but the world changed around it. In the player, the prediction prompt at such moments asks which node gets swallowed next — answerable by scanning the dashed frontier for the cheapest crossing edge, which is the entire algorithm performed by eye.

The invariant

The in-tree nodes always form a single connected blob, and the accepted edge set is a subset of some minimum spanning tree. Connectivity is by construction — every accepted edge has one end inside. The MST claim is the cut property applied at each acceptance: the cut is (in-tree, everything else); the algorithm takes a lightest crossing edge; the exchange argument (swap it into any MST lacking it, evicting a no-lighter edge from the induced cycle) shows some MST contains all accepted edges. V−1 acceptances later, the accepted set is that MST.

The heap’s supporting invariant: every boundary-crossing edge is in the heap (possibly alongside stale entries). It holds because a node’s edges are pushed the moment the node joins, and edges only become boundary-crossing when one end joins. Stale entries do not threaten correctness — they are filtered on pop — only the heap’s size, which is why the complexity is stated in E, not V.

Complexity, derived

Every edge is pushed at most twice (once per endpoint joining) and popped at most once each: O(E) heap operations at O(log E) = O(log V) apiece — O(E log V) time, O(E) heap space. With decrease-key (a Fibonacci or pairing heap, keyed per node) the bound improves to O(E + V log V), which matters in theory and rarely in practice. And on dense graphs the humble O(V²) array version — scan all nodes for the cheapest key each round — wins outright, having no log factor and no heap constant: worth saying aloud, because “which MST algorithm” answers differ by graph density, not by taste.

Prim versus Kruskal, summarised honestly: Kruskal pays a global sort, Prim pays heap traffic; Kruskal wants an edge list, Prim wants adjacency; sparse favours Kruskal, dense favours Prim (or its array form); both produce the same total weight, always.

What people get wrong

• Keying the heap on path cost — that is Dijkstra, and the output is a shortest-path tree, which is generally not an MST. The one-word difference is the classic trap, set deliberately in interviews.
• Skipping the stale-entry check: a popped edge whose far end is already in-tree must be discarded, or the “tree” gains a cycle.
• Pushing only the lightest edge per neighbour: without decrease-key, all crossing edges must be pushed; pruning early breaks the boundary invariant.
• Assuming the visual blob means BFS ordering: the frontier is priority-ordered by weight, and growth routinely jumps to the far side of the boundary.
• Comparing MSTs edge-by-edge across algorithms: with tied weights the sets can differ legitimately. Compare totals.

Implementation notes

The clean version mirrors Dijkstra’s shape exactly: a visited set, a heap of (weight, from, to), lazy deletion on pop, and a push of the new node’s edges after each acceptance. If you already have a working Dijkstra, the diff is: seed the heap with the start’s edges instead of (0, start), and push next.weight instead of d + next.weight. Writing both functions side by side and highlighting the diff is a legitimately strong interview move.

The array variant for dense graphs: keep key[v] = cheapest known edge from the tree to v; each round, scan for the minimum unvisited key (O(V)), add that node, then relax its edges into the keys (O(V)). Total O(V²), no heap, beautiful cache behaviour — and on complete graphs (E ≈ V²/2) it is the optimal choice, not a compromise.

Determinism and ties: with equal weights, acceptance order depends on heap tie-breaking. As with Kruskal, referee implementations against each other by total weight — this site’s unit suite runs Prim’s trace against a Kruskal reference (and vice versa) on shared seeds for exactly that reason.

The follow-up questions

Exactly what differs from Dijkstra? The heap key: edge weight versus accumulated distance. Same loop, same lazy deletion, same visited set — different problem solved. Understanding why the key change flips the semantics (MSTs care about connection cost, not travel cost) is the real question behind the question.

Why is the greedy choice safe? Cut property, exchange argument: the lightest edge crossing the (tree, rest) cut belongs to some MST, and that is the edge Prim always takes. No acceptance ever needs revisiting.

When Prim over Kruskal? Adjacency-list graphs, dense graphs, or when edges stream from a neighbour oracle. Kruskal when a sortable edge list is the natural form. On complete graphs, array-Prim at O(V²) beats both heap versions.

Can Prim start anywhere? Yes — any start node yields an MST, and with distinct weights the same MST. The start changes the acceptance order, never the total.