Minimum spanning trees: Prim

Connect every node as cheaply as possible. Prim = Dijkstra with the EDGE WEIGHT on the heap, not the distance.

Grow the tree across the cut

• Start with one node; everything else outside
• Repeatedly add the cheapest edge crossing tree ↔ outside
• The new node brings new crossing edges; repeat until all V nodes joined
• V−1 edges, no cycles, minimum total weight

Watch the tree grow

Green = in tree · dashed blue = cut candidates · orange = cheapest edge chosen. Total climbs by the smallest possible amount each step → 15.

"Minimum" is worth 3×

Same connectivity, same V−1 edges: arbitrary tree ~3× heavier than the MST.

Why greedy is optimal: the cut property

• Any cut splits nodes in two; the cheapest crossing edge is in some MST
• Prim's cut = "tree vs outside" → every edge it adds is provably safe
• Same theorem justifies Kruskal (different cuts)
• MST is NOT a shortest-path tree — don't route on it

Takeaway

One heap-key change turns shortest paths into cheapest connections. The math of cheap networks: grids, cables, pipes, clustering, TSP bounds. Next: Kruskal builds the same tree the opposite way — with union-find.