The problem, and why it is not a shortest path
We have spent this whole rung on one weighted-graph question — how to get cheaply from a source to everywhere else. The minimum spanning tree asks a sibling question that sounds similar but is genuinely different: given a connected, undirected graph with a weight on each edge, choose a set of edges that connects all the vertices together while making the total weight as small as possible. Picture towns that must all share one water network, and edges whose weights are the cost of laying pipe between two towns. You are not trying to reach one town fast; you are trying to wire up every town for the least total pipe.
The answer is a tree, and that is forced, not chosen. To connect n vertices you need at least n-1 edges, and a connected graph on exactly n-1 edges has no cycle — it is a tree, called a spanning tree because it touches (spans) every vertex. Any extra edge would close a cycle, and a cycle always contains an edge we could drop while staying connected. So the cheapest way to connect everything is necessarily acyclic. This is the first place the MST parts ways from single-source shortest paths: there the output was a shortest-path tree rooted at one source, optimizing distance from that root; here there is no root and no source, and we optimize one global number — the sum of chosen weights.
Two facts that decide every edge
Before any algorithm, learn the two facts that make MSTs tick, because together they tell you, for every edge, whether it is safe to take or safe to discard. First the cut property. A cut splits the vertices into two non-empty groups; an edge crosses the cut if its two endpoints land in different groups. The claim: for any cut, the cheapest edge crossing it belongs to some MST. Why? If a minimum spanning tree avoided that lightest crossing edge e, the tree must still cross the cut somewhere — say by a heavier edge f. Swap f out and e in. Both connect the two sides, so the result is still a spanning tree, and it weighs no more (e was no heavier than f). That swap is a textbook exchange argument: it shows refusing the lightest crossing edge never helps.
Now the mirror image, the cycle property: in any cycle, the heaviest edge belongs to no MST (assuming it is strictly heaviest). The argument is the same swap run backwards. If some MST contained that heaviest cycle edge, deleting it breaks the tree into two pieces — but the rest of the cycle still arcs across that break, so some other, lighter cycle edge can reconnect the pieces for less. The heaviest-in-a-cycle edge is always droppable. Put the two facts side by side and you have a complete decision procedure: the cut property tells you which edges you may safely add, the cycle property tells you which you may safely reject. Every MST algorithm is just a different schedule for applying these two rules.
Kruskal: sort the edges, take the cheap and safe ones
Kruskal's algorithm is the cut property read globally. Forget the structure for a moment and just sort every edge from cheapest to most expensive. Walk down that list and adopt an edge if and only if it joins two pieces that are not yet connected; skip it if both endpoints already sit in the same piece. You start with n lonely vertices (n separate fragments) and end with one tree once you have accepted n-1 edges. The whole method fits in a sentence: greedily grab the cheapest edge that does not create a cycle.
- Why each accepted edge is safe: when you take the cheapest remaining edge that joins two different fragments, consider the cut that puts one of those fragments on one side and everything else on the other. The edge you are about to add crosses that cut, and since you are scanning in increasing weight, it is the lightest edge crossing it that you have not already rejected — the cut property says it belongs to an MST.
- Why each skipped edge is safe: if both endpoints are already connected, adding the edge would close a cycle, and because you scanned in increasing order, this edge is the heaviest on that cycle. The cycle property says it belongs to no MST. So skipping loses nothing.
- The one hard part is testing 'are these two endpoints already in the same fragment?' fast, millions of times. That is exactly what a union-find structure does: find(x) returns which fragment x is in, and union(x,y) merges two fragments. Accept an edge precisely when find of its two ends differ, then union them.
The cost is dominated by the sort: O(m log m) for m edges, and since m is at most about n^2, log m is O(log n), so people usually write O(m log n). The union-find work is nearly free by comparison — with union by rank and path compression each operation is effectively a tiny constant, so the 2m find/union calls add only O(m * alpha(n)), where alpha is the inverse-Ackermann function that never exceeds about 4 in practice. Honest footnote: that union-find cost is amortized — it is the average over the whole sequence of operations, not a per-operation guarantee. A single union can still occasionally do more work; the bound promises the total stays nearly linear.
Prim: grow one tree outward, cheapest edge first
Prim's algorithm applies the very same cut property, but with a fixed cut that grows. Pick any start vertex and call it the tree. Repeatedly add the cheapest edge that has exactly one endpoint inside the tree and one outside, pulling that outside vertex in. The cut here is always 'vertices already in the tree' versus 'vertices not yet in', and the edge you add is by construction the lightest one crossing that cut — safe by the cut property, every single step. After n-1 such additions every vertex is in, and you have an MST. If this shape feels familiar, it should: it is the same outward-growing, frontier-expanding skeleton as Dijkstra.
But the resemblance to Dijkstra hides a crucial difference, and getting it wrong is a classic mistake. Dijkstra keys each frontier vertex by its distance from the source — the whole accumulated path length — because it is minimizing distance from a single root. Prim keys each frontier vertex by the weight of the single cheapest edge connecting it to the current tree, because it is minimizing the total set of chosen edges, not any path. Same engine, different key. Confuse the two and Prim stops finding the minimum spanning tree.
key[v] = lightest edge from v into the current tree (Prim)
key[v] = best known distance from the source to v (Dijkstra)
same loop: pop the min-key frontier vertex, then relax
its neighbors' keys. Only the key formula differs.Because the inner step always wants the smallest key, Prim runs on the same priority structure as Dijkstra. With a binary heap, each of the n extract-min operations and each of the up-to-m key decreases costs O(log n), for O(m log n) overall — the same headline figure as Kruskal. The practical split is the usual one: Prim with an adjacency list and a heap is natural for dense graphs and when edges arrive tied to vertices, while Kruskal is natural when edges are already sorted or live in a flat list. Both are correct; both are O(m log n); choose by the data you hold, not by a belief that one is universally faster.
Why greedy works here — and the honest limits
It is worth pausing on a genuine surprise: greedy is the right tool here, even though greedy fails on so much else. Taking the locally cheapest safe edge and never reconsidering gives the global optimum exactly — no backtracking, no second-guessing. That is rare. Greedy gives the optimum for interval scheduling and for Huffman coding, yet it fails outright for the 0/1 knapsack, where the locally best item ratio can lead you astray. 'Looks locally best' is never a proof of global optimality. The MST is trustworthy not because greedy feels right but because the cut and cycle properties prove each local choice is consistent with some global optimum.
There is a deeper reason the MST is so well-behaved, and it ties this whole greedy story together. The sets of edges that contain no cycle (the forests of the graph) form a structure called a matroid, and the matroid greedy theorem says: pick elements in increasing weight order, taking any that keep you inside the structure, and you are guaranteed the optimum. Kruskal is literally that theorem applied to the graphic matroid. So the greedy view of Prim and Kruskal is not a coincidence or a lucky pattern — it is an instance of a clean general law that says precisely when greedy may be trusted.
Two honest caveats to carry out the door. First, both algorithms assume an undirected graph; the directed analogue (the minimum 'arborescence') needs a different, more intricate method, so do not reach for Kruskal or Prim on a directed graph. Second, the O(m log n) figure is an asymptotic statement about scaling — it hides constants and assumes large inputs. As the broader rung warned, asymptotics describe how cost grows, not which code wins at a particular size; for a tiny graph the simplest implementation may beat the cleverest. Know the bound, but measure when size actually matters.