the greedy view of Prim and Kruskal
/ PRIM; KRUSS-kuhl /
Suppose you must connect a set of towns with roads so everyone is reachable, paying for the total length of road you build, and you want the cheapest such network. The cheapest connecting network with no wasteful loops is a minimum spanning tree. Two famous algorithms, Kruskal's and Prim's, both find one, and both are pure greedy — they add the cheapest edge they safely can, again and again, never reconsidering.
Kruskal's: sort all edges from cheapest to most expensive; scan them in that order; add each edge UNLESS it would form a cycle with edges already chosen; stop when the tree spans everything. Prim's: grow a single tree from a start vertex, each step adding the cheapest edge that connects the tree to a new vertex outside it. Both are greedy because each step takes a locally cheapest legal edge. Why does local-cheapest reach the global-cheapest tree? The cut property: for any way of splitting the vertices into two sides, the cheapest edge crossing that split is safe to include in some MST. The exchange argument behind it: if an MST omits that cheapest crossing edge, it must cross the split with a costlier edge; swap the costly crossing edge out and the cheap one in — still a spanning tree, and no more expensive — so an MST contains the cheap edge. Kruskal and Prim each just apply this safe-edge rule in a particular order, so both are correct.
The deeper reason MST is a perfect greedy problem is that its independent sets — the acyclic edge sets (forests) — form a matroid (the graphic matroid), and the matroid-greedy theorem guarantees greedy optimality there. This is why greedy works for MST but not for, say, the traveling salesman tour. Note the boundary of this field: the cut property, cycle property, and the union-find data structure that makes Kruskal efficient belong to the dedicated MST field; here the focus is purely on why these algorithms are correct greedy methods.
Triangle with edge weights AB=1, BC=2, AC=3. Kruskal sorts 1,2,3: add AB (no cycle), add BC (no cycle), reject AC (would close a cycle). MST = {AB, BC}, total 3. Prim from A: cheapest edge out of {A} is AB, then cheapest edge from {A,B} to outside is BC. Same tree.
Both algorithms repeatedly add a cheapest safe edge; the cut property (an exchange argument) proves each such edge belongs to some MST.
Greedy works for MST because forests form a matroid; it does NOT carry over to the traveling salesman tour, where greedily adding cheap edges can be far from optimal.