PRIM / JARNIK grow one tree, always grab the cheapest edge
A minimum spanning tree connects every vertex at the least total edge cost. This method grows a single tree from any start, repeatedly adding the cheapest edge that reaches a new vertex. It is usually called Prim’s — but Jarník had it in 1930, 27 years before Prim, and Dijkstra rediscovered it again in 1959.
THE TECHNIQUE cheapest edge out of the growing tree
Keep, for every vertex not yet in the tree, the cheapest single edge connecting it to the tree (its key). Each step: pull in the vertex with the smallest key, add that edge, then relax its neighbours’ keys. After V steps the tree spans everything. Run it on a small weighted graph; chosen edges glow. live demo
HISTORY & CREDIT 27 years before the name on it
“Prim’s algorithm, 1957” — the method is Prim’s Jarník’s, published in Czech in 1930 and overlooked. cited
1926 · Otakar Borůvka gives the first MST algorithm of any kind (a parallel, edge-contracting method) — to electrify Moravia efficiently. 1930 · Vojtěch Jarník publishes the grow-one-tree method — the true first form of “Prim’s.” In Czech, so the West missed it. 1957 · Robert C. Prim (Bell Labs) rediscovers it independently; 1959 · Edsger Dijkstra rediscovers it a third time. the point · the plain version scans for the minimum linearly — O(V²), no heap — and that is optimal for dense graphs.
Three independent inventors, one algorithm; the earliest gets the smallest share of the name. Jarník 1930, not Prim 1957
RECOMMEND FOR I-13 three arrays, a linear min-scan
Exactly Dijkstra’s (dart 055) skeleton — key[], inMST[], parent[] as bounded arrays, a linear scan for the minimum — and the MST weight comes out on the compiler:
$ i13 run prim.i13 # 5-vertex weighted graph, start at A
total = 16 # MST edges A-B(2), B-C(3), B-E(5), A-D(6)
Recommend:nothing new — it runs on the same array skeleton as Dijkstra (055): key[v] the cheapest edge into the tree, inMST[v] a 0/1 flag, a linear scan for the min (O(V²), no heap — which is the dart’s point, and optimal for dense graphs). Vertex indices are exact f64 integers. Note: the graph itself wants a 2-D weight matrix (PS-004) — here flattened to W[i*V+j] — and a heap would drop it to O((V+E) log V) via heap-on-array (PS-005, closed by dart 062). Neither is needed for the clean build.