The cheapest network that connects everything. Start at one vertex, and forever add the single cheapest edge that leaves the tree you have. No backtracking, no global search — a local greedy grab, repeated, provably lands on the minimum spanning tree. Down the center, data flows: a weighted graph goes in, the tree grows edge by edge, the minimum comes out. The blue team builds and defends it; the red team tries to break it.
source R. C. Prim, Shortest Connection Networks And Some Generalizations, Bell System Tech. J. 36 (1957) 1389–1401 — archive.org/details/bstj36-6-1389. Rendered, not quoted.
One invariant runs the whole algorithm — the cut property: pick any way of splitting the vertices into "in the tree" and "not yet", and the cheapest edge that straddles that split is always safe to add. Prim just applies it repeatedly, seed outward.
Live state of the current run — edges added, and the frontier the cut property is choosing across:
| step | edge added | weight |
|---|
Prim (1957) grows one tree by always taking the cheapest edge across the cut between grown and ungrown. Kruskal sorts all edges and greedily merges forests, refusing any that closes a cycle. Two strategies, one theorem — both are the cut property in disguise, and on distinct weights they land on the same tree.
The idea is older than the name: Vojtěch Jarník published it in 1930; Prim rediscovered it in 1957; Dijkstra again in 1959. Each sphere is the next one's premise.
The blue team's live check: recompute the tree and compare its weight against the brute-force minimum over every spanning tree, and against Kruskal. If red switches the greed to MAX, this badge is where it shows.
A small constructed graph: 5 vertices (A–E), 7 undirected edges, all weights distinct so the minimum spanning tree is unique. This is what feeds the panel below.
| edge | weight | edge | weight |
|---|---|---|---|
| B — C | 1 | B — D | 4 |
| A — B | 2 | C — D | 5 |
| A — C | 3 | C — E | 6 |
| D — E | 7 |
Connected, so a spanning tree exists; distinct weights, so exactly one is minimum. That is the whole input — no hidden numbers.
Each step, the engine scans the frontier and grabs the cheapest leaving edge — dashed cyan are candidates, green is the one chosen, teal are locked into the tree.
Change the seed — the tree may grow in a different order, but the final tree and its weight are computed from the graph on the spot, and they never change.
What the machine produces, proven: a spanning tree — connected, exactly 4 edges (|V|−1), acyclic — of minimum total weight 13, matching the brute-force minimum over all spanning trees of this graph. Prim and Kruskal agree to the number.
The blue team's witness (left) confirms this against brute force live; the red team (right) tries to make it lie.
Prim answers exactly one question — least total edge weight to connect a fixed vertex set — and answers it perfectly. Ask a neighbouring question and the same greed gives a confidently wrong tree.
"Prim finds the shortest path between two nodes." Cut. That is Dijkstra. Prim minimizes the whole tree's weight; the tree path between two vertices can be far longer than their true shortest path.
"Prim invented the algorithm." Kept, corrected. Jarník published it in 1930, Prim in 1957, Dijkstra in 1959 — it is fairly the Jarník–Prim algorithm.
"The minimum spanning tree is unique." Cut. Only when edge weights are distinct. Ties allow several MSTs of equal weight — this graph is built with distinct weights precisely so the answer is one tree.
The red team's move: flip the greed. Instead of the cheapest leaving edge, add the most expensive one each step — still a spanning tree, but now the maximum. The blue team's witness (window 7) is watching the weight.
Switch to the maximum leaving edge and the tree's weight climbs to 20 — above the true minimum of 13. The witness recomputes against brute force, disagrees, and turns red. Nothing is faked; the attack is real and it is caught.