Prim's algorithm
/ PRIM /
Where Kruskal's algorithm scatters cheap cables across the whole map and merges islands, Prim's algorithm grows a single connected blob outward from one starting town, like spilled water spreading. At every moment it has one connected tree, and it asks: of all the cables that lead from my current tree to a town not yet in it, which is the cheapest? It adds that one, swallowing the new town, and repeats until every town has been absorbed.
Concretely: pick any start vertex; its tree initially holds just that vertex. Keep, for every vertex outside the tree, the cheapest single edge connecting it to the tree (use a priority queue keyed by that cost). Repeat V-1 times: extract the outside vertex with the smallest connecting cost, add it and that edge to the tree, then update its neighbors' best connecting costs. Correctness is the cut property applied over and over: the tree built so far is one side of a cut, and Prim always adds the minimum-weight edge crossing that cut, which is exactly the safe edge the cut property guarantees. With a binary heap the cost is O(E log V); with a Fibonacci heap, O(E + V log V), which is asymptotically better on dense graphs.
Prim's tends to win on dense graphs (many edges), where Kruskal's up-front sort of all edges is expensive, while Kruskal's is natural on sparse graphs or pre-sorted edges. Both produce a minimum spanning tree; they just grow it differently — Prim's one expanding tree versus Kruskal's many merging forests. A frequent confusion to clear up: Prim's looks almost identical to Dijkstra's algorithm and even uses the same priority-queue machinery, but the key it minimizes is different. Prim's queues each vertex by the weight of the single cheapest edge attaching it to the tree; Dijkstra's queues by total distance from the source. Same skeleton, different quantity — and they solve different problems.
Start at A. Tree {A}; cheapest edge out is A-B (1) -> add B. Tree {A,B}; cheapest exiting edge is B-C (2) -> add C. Tree {A,B,C}; exiting edges are A-C (3, internal-skip), C-D (4), B-D (5); cheapest is C-D (4) -> add D. All vertices in; MST weight 1+2+4 = 7, the same tree Kruskal's found by a different route.
Prim grows one tree, always adding its cheapest exiting edge — the cut property's safe edge for the cut between tree and rest.
Prim's and Dijkstra's share the same priority-queue skeleton but minimize different keys: Prim's by the single edge attaching a vertex to the tree, Dijkstra's by total distance from the source. Do not conflate them.