◄ WORLD V · SONNY 5DART 525 · a helldive at the net

KRUSKAL the cheapest tree — add the smallest edge that does not close a loop

A minimum spanning tree connects every node with the least total edge weight — the cheapest way to wire a network with no redundant loops. Kruskal’s algorithm (1956) builds it greedily and globally: sort all edges by weight, then add each in turn unless it would form a cycle — and union-find (dart 518) is exactly the cycle test (endpoints already in the same set). Take the cheapest safe edges and you have the optimum, provably. It pairs with Prim (dart 526), which grows the tree locally; both reach the same minimum weight. Here that weight is 7.

THE TECHNIQUE sort edges; add the cheapest that joins two different sets (union-find)

The demo builds an MST by adding the cheapest cycle-free edges (via union-find) — total weight 7: live demo







  
HISTORY & CREDIT Joseph Kruskal · 1956

  
“Greedy algorithms give approximate answers.” — for the MST, taking the cheapest safe edge each time is provably optimal. cited

  
the sort · order all edges by weight, cheapest first.
the add · take each edge unless its endpoints are already connected (union-find cycle test).
1956 · Joseph Kruskal — the cheapest spanning tree, provably optimal.

  
A network wired at least cost by taking cheap edges and refusing loops — greedy, and exactly optimal. resource






  
RECOMMEND FOR I-13 the MST weight, on the compiler

  
On the canonical compiler, Kruskal (cheapest cycle-free edges via union-find) builds an MST of total weight 7:

  
$ i13 run nw_kruskal.i13   # cheapest non-cycle edges (union-find)
RUN OK · 623 step(s) · peak stack 18 · call depth 9
mst_weight = 7

  
Recommend as a NULL — a greedy optimum, resource-shaped. Kruskal computes the minimum spanning tree weight (forall-pinned by the graph, B39) greedily with union-find (B40). Its optimality is a theorem (the cut property). No new invariant. NULL — the cheapest tree, and the twin of Prim (dart 526).