Programming

Minimum Spanning Tree

It is not a cautious hoarder picking cheap twigs. It is the geometric miracle of a matroid: short-sighted, local greed is mathematically guaranteed to carve out the globally optimal skeleton without a single step of regret.

Cayley counts 10^196 spanning trees for 100 cities; Kruskal finds the cheapest in 60,700 comparisons without regret.

Mission 18about 11 min

Connect isolated network nodes with minimal total link weight using greedy cut welding and cycle checks.

  1. Predict whether Kruskal's edge sort and Prim's growing wave can pick different edge sets of equal weight
  2. Step the GraphCanvas to watch accepted edges weld islands into a single connected component
  3. Take the boss round bet on how the cut property proves a greedy choice can never be regretted

After thisYou will design optimal physical cabling, cluster topologies, and approximations for the metric TSP.

Short on timeStep the GraphCanvas to watch Kruskal weld components together and verify the final weight of 6.

Two Greedy Orders, One Forced Weight

3 minthe hook

Exactly 2 of the 24 spanning trees on this six-vertex board weigh 6. At , Cayley’s 1889 formula counts trees, so enumeration is not a plan.

Kruskal needs about 60,700 comparisons to find one. One algorithm sorts all edges globally; the other grows a single tree outward from vertex A.

Call the picture the welding archipelago: islands are vertices, bridges are edges, and each accepted edge welds two separate islands. The cut, the set of bridges leaving one island for another, is the certificate that the cheapest weld is safe.

A minimum spanning tree whose welds are the cheapest edges across their cutseach weld is the cheapest bridge across its cutABDEFC12312112cutsafeweld · MST, 5 edges, total 6other bridgescut at the last Prim weld C–F · weights from the page
The tree both panels build on this graph: five welds, total weight 6. Dashed bridges were rejected; the bracket marks the cut at the last weld, C–F.

Watch the component chips: every accepted edge joins two separate components, and that cut is why the choice can never be regretted.

Before you touch the transport, commit to a prediction below.

1 / 10
Kruskal
12312112ABDEFC

1/10 Kruskal: sort 8 edges by weight, then test each for a cycle

components{A}{B}{D}{E}{F}{C}
  1. 1 Kruskal: sort 8 edges by weight, then test each for a cycle

Kruskal. The transport is yours; nothing autoplays. Step once and the log sorts all eight edges by weight, then walks that order and asks a single question at each edge: are the two endpoints already in one component?

1 / 7
Prim · source A
12312112ABDEFC

1/7 Prim: grow one tree from A; it is a single component by construction

treeA
  1. 1 Prim: grow one tree from A; it is a single component by construction

Prim, same eight edges, starting at A. This player never sorts anything: it keeps one blob and repeatedly takes the cheapest edge leaving that blob. Watch the chip row — it holds the vertices already swallowed, not the components.

Both panels operate on the exact same graph. The left player sweeps a globally sorted list; the right player expands a connected component from vertex A.

Kruskal sweeps globally sorted edges, while Prim grows a local cluster from vertex A. Can their final trees finish with different total weights?

NextWhy do Kruskal and Prim arrive at the exact same tree weight from opposite greedy directions?

The Mystery of Unregretted Greed

2 minthe trap

Greedy algorithms usually fail. In almost every combinatorial puzzle, seizing the immediate best local option leads directly to a suboptimal dead end.

Yet for spanning trees, greed never fails. You can sort edges globally and greedily pick non-cycles, or expand locally and greedily take the cheapest exit; both arrive at mathematical perfection.

The real question is not how to write these five lines of code. It is why a choice made at step two is never regretted at step ten, and what geometric structure makes that possible.

NextHow does Whitney's matroid exchange axiom guarantee that greedy edge choices are unregretted?

Whitney’s Matroid and the Axiom of Exchange

2 minthe invariant

A matroid is a finite ground set of elements together with an independent set system satisfying three conditions (Whitney 1935):

  • The empty set is independent: .
  • Heredity: if and , then .
  • The exchange axiom: if with , there exists an element such that .

Whitney formulated this in 1935 to generalize linear independence from vector spaces to combinatorics. A smaller independent set can always absorb an element from a larger one without losing independence.

In a graph, let be the edge set and declare an edge subset independent if and only if it is acyclic (a forest). A maximal independent set is a spanning tree, and the resulting structure is the graphic matroid. A minimum spanning tree is simply a minimum-weight basis of this matroid.

To verify the exchange axiom on graphs, consider two forests and with . Forest has connected components, while has components, meaning partitions vertices into strictly more pieces. Because , some edge must connect two distinct components of , ensuring remains an acyclic forest.

NextHow do the fundamental cut and cycle duals certify the optimality of every welded edge?

The Cut and Cycle Duals

2 minthe algebra

Two fundamental theorems govern spanning trees, serving as dual expressions of Whitney’s exchange axiom:

Cut property. Partition vertices into two non-empty sets and . The lightest edge crossing this cut belongs to some minimum spanning tree. If it is uniquely lightest, it belongs to every minimum spanning tree.

Cycle property. In any simple cycle , the strictly heaviest edge cannot belong to any minimum spanning tree.

Consider triangle A–B–D on screen with weights 1, 2, and 3. Edge B–D weighs 3, making it strictly the heaviest edge on that cycle.

Cycle A–B–D has edge weights 1, 2, and 3. Can edge B–D (weight 3) ever appear in an MST of this graph?

The two theorems are two aspects of a single reality: an edge is safe when it is lightest across a cut, and eliminated when it is heaviest around a cycle.

Where greed shatters: the knapsack trap. Matroid structure is the exact boundary where greed works. Remove the exchange axiom, and greed collapses immediately:

  • Consider items with weights and values , with knapsack capacity 10.
  • A greedy strategy picks value 8 (weight 6) first, blocking the remaining items and scoring 8.
  • The optimal solution selects the two items of weight 5, scoring .

The knapsack system fails Whitney’s exchange axiom. With independent sets of size 1 and of size 2, no item from can augment . That failure is why 0/1 knapsack is NP-hard (Karp 1972) while MST runs in near-linear time.

NextHow did Borůvka's 1926 electrification algorithm power the rural cities of Moravia?

The Twin Skeletons: Kruskal and Prim in Lockstep

2 minthe simulation

Both panels finish at five edges with total weight 6, but their logs reveal distinct routes:

  • Kruskal accepts edges in order: A–D (1), B–E (1), E–F (1), C–F (1), A–B (2), while rejecting cycles D–E, E–C, and B–D.
  • Prim grows outward from A: A–D (1), A–B (2), B–E (1), E–F (1), C–F (1).

Their shared total is guaranteed by matroid theory. Whether their chosen edge sets match depends entirely on arbitrary tie-breaking between equal-weight edges.

1 minboss round

There are 24 distinct spanning trees on this 6-vertex graph. Is the minimum spanning tree unique?

Four edges — A–D, B–E, E–F, C–F — sit in every minimum tree. Each is the unique cheapest edge across a cut, pinned by the cut property.

The chart below measures key comparisons across three implementations on seeded random graphs with .

Edge-weight comparisons to build one MST, measured (m = 3n, mean of 20 seeded graphs)

1e11e21e31e41e5050100150200250nodes nweight comparisons
Kruskal, sort + union–find (measured)Prim, rescan every edge each step (measured)Prim, binary heap (measured)m·log₂m (reference)

Kruskal tracks closely because sorting dominates runtime. Rescanning Prim examines every edge per added vertex, growing quadratically, while a binary heap restores performance to near-sorting speeds.

NextWhat linear-time verification algorithms inspect minimum spanning trees without sorting?

Electrifying Moravia: From Clusters to Traveling Salesmen

2 minsystems

Kruskal’s cycle check uses disjoint-set union–find. Sorting edges costs , followed by operations costing , absorbing union–find cost into sorting:

Borůvka conceived the first MST algorithm in 1926 to plan the regional electrical network of Moravia. His algorithm grows components in parallel, halving the component count each round. This parallel structure remains the standard method for graph connectivity in modern distributed systems (Kiveris et al. 2014).

Removing the heaviest edges from an MST partitions vertices into optimal clusters, which is single-linkage clustering (Gower and Ross 1969). Christofides (1976) used an MST to guarantee a 1.5-approximation for the metric Traveling Salesperson Problem.

Next missionLongest Common Subsequence4,225 cells replace 2^32 brute-force candidates: how git diff extracts identical lines from diverging files.

The Frontier of Linear Time and Matroid Intersections

Chazelle (2000) established an deterministic MST algorithm using soft heaps. Pettie and Ramachandran (2002) discovered an algorithm with provably optimal runtime, although its exact mathematical complexity remains an open problem.

When an optimization problem requires independence across two matroids simultaneously, simple greed fails. Edmonds (1979) solved matroid intersection using augmenting paths, bridging bipartite matching and network synthesis.

Attributions

  • Whitney 1935 — On the abstract properties of linear dependence: matroids and the exchange axiom. The object this page is about.
  • Borůvka 1926 — the first minimum spanning tree algorithm, and the halving structure behind parallel and distributed versions.
  • Jarník 1930 — the blob-growing algorithm, later rediscovered as Prim’s. Pair it with Prim 1957 in any honest history.
  • Kruskal 1956 — the sorted sweep, and the union–find phase it needs.
  • Prim 1957 — the textbook presentation of Jarník’s algorithm that gave it the common name.
  • Rado 1957 · Edmonds 1971 — greedy is optimal on a matroid, and on nothing weaker. The exchange argument in section 3 is theirs.
  • Karp 1972 — 0/1 knapsack is NP-hard, which is the price of losing the exchange axiom.
  • Gower and Ross 1969 — an MST with its heaviest edges removed is single-linkage clustering. Christofides 1976 — the MST-based 1.5-approximation for the travelling salesman.
  • Karger, Klein and Tarjan 1995 · Chazelle 2000 · Pettie and Ramachandran 2002 — randomized linear time, , and the optimal deterministic algorithm respectively.
  • Kiveris and others 2014 — Borůvka-style connectivity in MapReduce, where the MST structure reappears under a different machine model.