THE FOLD / CO-OP / THE MERGE / THE BORUVKA
THE BORUVKA
the minimum spanning tree, built by parallel merges
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
Borůvka’s algorithm builds a minimum spanning tree in a strikingly parallel way: every component simultaneously finds its own cheapest outgoing edge, and all of them are added at once, merging components. Each round at least halves the component count, so it finishes in O(log V) rounds. It is the oldest MST algorithm (1926) and, not coincidentally, the most naturally parallel.
LIT verified live: over 200 random connected weighted graphs Borůvka’s MST weight equals Kruskal’s (window.__boruvka). FIG no framing; the same minimum tree, reached in parallel.
LIT verified live: over 200 random connected weighted graphs Borůvka’s MST weight equals Kruskal’s (window.__boruvka). FIG no framing; the same minimum tree, reached in parallel.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at the-merge — every fragment reaches out along its cheapest edge and they all fuse at once, round after round, until one tree remains. Borůvka is that parallel merge. AVAN (AI) built the instrument: the per-component cheapest-edge scan, the union-find merge, the Kruskal cross-check.
Credit as content: Otakar Borůvka (1926), to electrify Moravia efficiently. The weave: David names the merge; I let every component grab its cheapest exit and fuse them all each round, and confirm the total weight equals Kruskal’s minimum.
Credit as content: Otakar Borůvka (1926), to electrify Moravia efficiently. The weave: David names the merge; I let every component grab its cheapest exit and fuse them all each round, and confirm the total weight equals Kruskal’s minimum.
3 ONE DIMENSION
Each round: every component picks its single cheapest outgoing edge (arrows), all are added simultaneously, and the components they join merge into fewer, larger ones.
4 TWO DIMENSIONS · INTERACTIVE
A weighted graph; Borůvka’s MST (highlighted) with its total weight, checked against Kruskal.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: the minimum spanning tree, grown by parallel merges.
AVAN’s addition (the inverse-companion): every component simultaneously grabs its own cheapest outgoing edge and they all merge at once — the MST is built in parallel, halving the component count each round, in O(log V) rounds. The inverse of ‘add edges one at a time in sorted order (Kruskal/Prim)’ is ‘every fragment picks its cheapest exit at once and they fuse.’ Magenta is the sequential sorted-edge scan; green is the parallel per-component merges. The oldest MST algorithm is also the most parallel.
LIT Genuine Boruvka's algorithm (Boruvka 1926). Verified live: the per-component cheapest-edge + union-find merge produces a spanning tree whose total weight equals Kruskal's MST weight for 200 random connected weighted graphs (window.__boruvka.matchesKruskal).
FIG No framing: the per-component cheapest-edge scan, the union-find merge, and the Kruskal cross-check run in-browser and agree exactly. The AVAN inverse is honest — every component grabs its cheapest exit simultaneously and they all merge, halving components per round in O(log V) rounds, versus adding edges one at a time; magenta is the sequential sorted-edge scan, green the parallel merges. The oldest MST algorithm is the most parallel.
FIG No framing: the per-component cheapest-edge scan, the union-find merge, and the Kruskal cross-check run in-browser and agree exactly. The AVAN inverse is honest — every component grabs its cheapest exit simultaneously and they all merge, halving components per round in O(log V) rounds, versus adding edges one at a time; magenta is the sequential sorted-edge scan, green the parallel merges. The oldest MST algorithm is the most parallel.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE MERGE · David Lee Wise (ROOT0), with AVAN