Minimum Spanning Tree (Prim's & Kruskal's)

What a spanning tree is, and why "minimum" matters

Given a connected, undirected, weighted graph, a spanning tree is a subset of its edges that connects every vertex, contains no cycles, and (as a direct consequence of those two properties) uses exactly V - 1 edges. A graph generally has many possible spanning trees; a Minimum Spanning Tree (MST) is one whose edges sum to the smallest possible total weight. This is the "connect everything as cheaply as possible" problem: wiring up a network, laying roads between cities, or connecting circuit components with minimum total cable — you need every node reachable, but you don't care about the individual node-to-node distances the way Shortest Paths does, only the total cost of the connecting structure.

This is a genuinely different optimization goal from Shortest Paths (Graphs topic), even though the two algorithms you'll use here (Prim's and Kruskal's) look structurally similar to Dijkstra's and Union-Find respectively. Keep the distinction sharp: shortest paths optimize source-to-destination cost; MST optimizes total network cost.

Prim's algorithm — grow one tree from a heap frontier

The idea: start from an arbitrary vertex, and greedily grow a single tree by always adding the cheapest edge that connects a vertex already in the tree to a vertex not yet in the tree. A min-heap keyed on edge weight makes "find the cheapest frontier edge" efficient — this is structurally almost identical to Dijkstra's, with one crucial difference in the priority key.

The key difference from Dijkstra, stated precisely: Dijkstra's heap key is dist[source] + weight — cumulative cost from the source. Prim's heap key is just weight — the cost of the single edge that would pull this node into the growing tree, with no memory of how far the source is. This is exactly why Dijkstra answers "cheapest way to reach each node from one origin," while Prim's answers "cheapest way to connect this node to the tree we've already built," regardless of origin — Prim's, in fact, produces the same MST no matter which start vertex you pick (assuming edge weights are unique; ties can yield different, equally-minimal trees).

Kruskal's algorithm — sort edges, grow a forest with Union-Find

The idea: sort all edges by weight ascending, then walk through them one at a time, greedily accepting an edge if and only if its two endpoints are not already connected — accepting it would otherwise close a cycle, which a tree can never contain. "Not already connected" is precisely the question Union-Find answers in near-O(1), which is why Kruskal's is essentially Redundant Connection's cycle check, run with a cost-minimization goal layered on top.

Instead of growing one tree vertex-by-vertex like Prim's, Kruskal's grows a forest of many small trees that gradually merge — at any point mid-algorithm, the accepted edges so far may form several disconnected tree fragments, which is exactly what Union-Find is designed to track.

The intuition behind correctness, briefly

Two classical properties justify why the greedy choice in both algorithms is always safe (full formal proofs aren't expected in an interview, but the intuition is worth being able to state):

• Cut property (justifies Prim's): for any partition of the vertices into two non-empty groups, the minimum-weight edge crossing between them must belong to some MST. Prim's frontier — vertices in the tree vs. not — is exactly such a partition at every step, so always taking the cheapest crossing edge is always safe.
• Cycle property (justifies Kruskal's): for any cycle in the graph, the maximum-weight edge on that cycle is never required in any MST (some other edge could always replace it without increasing total cost). Kruskal's, by processing edges cheapest-first and rejecting any edge that would close a cycle, is implicitly always rejecting what would have been that cycle's most expensive edge.

Prim's vs. Kruskal's: which to reach for

	Prim's	Kruskal's
Grows	One tree, vertex by vertex	A forest, merging fragments
Data structure	Min-heap	Sorted edge list + Union-Find
Time (typical, sparse graph)	O(E log V)	O(E log E) — dominated by the sort
Time (dense graph, adjacency matrix)	O(V²) without a heap — often faster than the heap version when E ≈ V²	O(E log E), no faster on dense graphs
Most natural input shape	Adjacency list, or an implicit graph (e.g., "cost between any two points" computed on the fly)	Explicit edge list
Easiest to implement when	You already have Dijkstra's pattern fresh and just need to swap the priority key	You already have Union-Find fresh and just need to add sorting

In practice: Kruskal's + Union-Find is the more common interview default, because most problems hand you (or let you cheaply construct) an edge list, and the "sort, then union-find cycle check" shape is short and easy to get right under pressure. Reach for Prim's when the graph is dense (near-complete, as in "connect these n points" problems where every pair is a potential edge) or when you're given an adjacency-matrix-style input, since Prim's O(V²) form avoids ever materializing the O(V²) edge list Kruskal's sort would need to touch.

Complexity, precisely

Algorithm	Time	Space
Prim's (binary heap, adjacency list)	O(E log V)	O(V + E)
Prim's (no heap, adjacency matrix, dense graph)	O(V²)	O(V²)
Kruskal's	O(E log E) — sorting dominates; equivalently O(E log V) since E ≤ V²	O(V + E) for the Union-Find structure and edge list

Both produce a total weight that is provably identical for any MST of the same graph (the minimum total weight is unique, even when the specific set of edges achieving it is not, which happens when equal-weight edges create ties).

Pitfalls and interview gotchas

• Disconnected graphs have no spanning tree at all. Both algorithms need an explicit check: Prim's should verify it visited all n vertices; Kruskal's should verify it accepted exactly n - 1 edges. Skipping this check silently returns a "minimum forest" total instead of correctly reporting impossibility.
• Self-loops. An edge from a vertex to itself can never usefully belong to a spanning tree (it doesn't connect two distinct components) — filter these out, or note that Union-Find's cycle check will naturally reject them anyway since find(u) == find(u) trivially.
• Multi-edges (parallel edges between the same pair). Not a correctness problem for either algorithm — Kruskal's sorted order simply considers the cheaper of two parallel edges first and the more expensive one will always fail the union-find check afterward — but make sure your representation doesn't accidentally deduplicate and silently drop the cheaper option.
• Forgetting union by rank/size in the Union-Find backing Kruskal's. Without it, find calls can degrade meaningfully on adversarial inputs — the whole point of pairing Kruskal's with a well-implemented Union-Find is to keep the cycle check near-O(1).
• Confusing MST weight with shortest-path distance. A vertex can be "cheap to add to the MST" (a low-weight edge from the current frontier) while still being many hops and a large cumulative distance away from an arbitrary source — MST says nothing about point-to-point distance, only total connection cost. Interviewers sometimes probe this distinction directly by asking "does the MST give you the shortest path between any two nodes?" (No — not in general.)
• Assuming there's always a unique MST. If edge weights are all distinct, the MST is unique. With tied weights, multiple different edge sets can achieve the same (unique) minimum total weight — both are "correct" answers if a problem asks you to construct one, but this matters a great deal for problems like "is this edge in every possible MST?" (critical) vs. "is this edge in at least one possible MST?" (pseudo-critical).
• LeetCode's MST-tagged problem pool skews Medium/Hard with almost nothing at Easy. Unlike BFS/DFS or even Union-Find, there's no canonical easy warm-up here — expect every practice problem below to require you to first recognize the disguised MST framing (points on a plane, wells and pipes, water rising over a grid) before you can even start applying Prim's or Kruskal's.

Where this reappears

The Union-Find machinery underneath Kruskal's is the same structure from Graphs → Union-Find — if any part of the union/find implementation above felt unfamiliar, that's the place to go back to. The heap-frontier machinery underneath Prim's is the same one Dijkstra used in Shortest Paths, with the priority key as the only real change — a good way to stress-test your understanding of both is to explain, out loud, exactly which one line of code differs between your Dijkstra and your Prim's implementation.