Minimum Spanning Tree
01 / The shared mechanism
A minimum spanning tree is the cheapest way to connect every node of a weighted, undirected graph — exactly N − 1 edges, no cycles, minimum total weight. Two classic ways to grow it: Kruskal walks the edges sorted by weight and uses union-find to skip any edge that would close a cycle. Prim starts at one node and uses a min-heap to repeatedly absorb the lightest edge crossing the current tree.
01 / The one-sentence essence
A spanning tree grows out of a seed node, one edge at a time, by always absorbing the lightest edge that crosses from the current tree to an unvisited node — a min-heap of candidate crossing edges does the bookkeeping, and an N − 1 round loop finishes the tree.
Problemminimum spanning tree of a weighted undirected graphGraphmeshSeed0
Graph has 6 nodes. Pick a seed and grow the tree by absorbing the lightest crossing edge each round.
step
0 / 7
heap
—
tree
0 / 6
total
0
0 / 7
02 / The pattern signature
# Prim's MST — grow the tree from a seedvisited ← {s}pq ← min-heap of (w, s, v) for (v, w) in neighbors(s)mst ← [ ], total ← 0while pq not empty and |visited| < N:(w, u, v) ← pq.pop_min() # lightest crossing edgeif v in visited: continue # stale; both ends already in treevisited.add(v); mst.append((u, v, w)); total += wfor (x, w') in neighbors(v): # push new frontier edgesif x not in visited:pq.push((w', v, x))
03 / When to recognize this pattern
"minimum spanning tree from a seed"
You want to connect every node of a weighted undirected graph as cheaply as possible and the graph is presented to you as an adjacency list — Prim starts at any one node and grows outward, a perfect fit when the topology lives in {node → neighbors}.
"dense graph (E ≈ N²)"
When edges nearly fill the N × N matrix, Prim wins. With a binary heap it runs in O(E log V); with an array-PQ variant it touches O(V²) — both beat sorting all E ≈ V² edges from scratch like Kruskal does.
"network of cables / pipes"
Wiring up cities, laying fiber, joining clusters — anything where the objective is "every node reachable, minimum total wire length." The seed-and-grow story maps directly onto how you'd actually lay the cable.
"add an edge to maintain connectivity"
When a question phrases growth one edge at a time and asks for the cheapest such growth, Prim's cut-and-absorb loop matches the narrative more faithfully than Kruskal's sort-and-merge.
04 / Common pitfalls
i.
Pushing edges to already-visited nodes back onto the heap.
Every time you absorb a node, you push all of its outgoing edges — but many neighbors are already in the tree. If you don't guard with
if v not in visited before pushing, the heap balloons with stale entries and memory plus log-factor cost both inflate. Filter on push (cheap) and still skip stale pops (cheap) — both are correct, and both are commonly needed.ii.
Confusing Prim with Dijkstra.
They look identical — graph, min-heap, visited set, while loop — but the key in the PQ is fundamentally different. Dijkstra stores
dist[v], the cumulative distance from the source; Prim stores just w, the single edge weight crossing the cut. Cross-wire them and you'll compute the wrong thing on the same graph without any error message.iii.
Using an adjacency matrix on a sparse graph.
The classic array-PQ Prim is O(V²) regardless of edge count — great when E ≈ V², wasteful when E ≪ V². If your graph is sparse, stick with adjacency lists + binary heap for O(E log V), or use Kruskal's edge-list + union-find for the same bound.
05 / Go practice — on LeetCode
Four problems, ordered by difficulty. No solutions here, by design.
— / When to use which
Kruskal
Use when the graph is given as an edge list and you already lean on a Union-Find structure — sort edges by weight, walk through, accept any edge whose endpoints are in different components. Edge-centric; needs no adjacency at all.
edge list + union-find · LC 1135 · LC 1489
Prim
Use when the graph is given as an adjacency list or the edge count is quadratic in N (dense graph). Start at any node, push its outgoing edges into a min-heap, repeatedly pop the cheapest edge that lands on an unseen node. Node-centric; the tree grows from a seed.
adjacency + min-heap · LC 1168 · LC 1584