MST — Prim's Algorithm
MST — Prim's Algorithm: build a minimum spanning tree by growing one tree outward from a start vertex.
- 1 <= V <= 10⁵
- V-1 <= E <= 10⁵
- 1 <= weight <= 10⁶
- Graph must be connected for a spanning tree to exist
Intuition
MST Prim's algorithm builds a minimum spanning tree by growing a single connected tree outward from an arbitrary starting vertex, repeatedly absorbing whichever outside vertex is cheapest to attach.
That single-tree property is the whole difference from Kruskal's, which takes globally cheapest edges wherever they fall and maintains a scattered forest until the pieces merge. Prim's partial result is always connected, which makes it a natural fit for dense graphs and for situations where you want a valid partial tree at every step.
The state each vertex carries is small: key[v], the cost of the cheapest single edge joining it to the current tree. Vertices start at infinity except the seed at zero. Each round takes the unabsorbed vertex with the smallest key, adds that cost to the total, and marks it in-tree.
Absorbing a vertex can only improve its neighbours' keys, so relaxation is local:
- After absorbing u, set key[v] = min(key[v], weight(u, v)) for each neighbour v still outside the tree.
Why taking the cheapest boundary edge is always safe is the cut property: for any partition of the vertices, the lightest edge crossing it belongs to some minimum spanning tree. The tree-versus-rest split is exactly such a partition, and the smallest key is exactly the lightest edge crossing it — so every step takes an edge that some MST contains.
With a binary heap this is O(E log V), which is why Prim's and Kruskal's usually land in the same complexity class despite their different shapes.
Grow one tree outward, always absorbing the cheapest edge that leaves it. Kruskal sorts all edges globally and needs union-find; Prim keeps a frontier heap and needs only a visited array. On dense graphs Prim wins; on sparse edge lists Kruskal is simpler.
Approach
Before reading on: price up what the direct approach costs here, then ask which edge is always safe to take across a cut. Aim for O(E log V) time and O(V + E) space.
Grow one connected tree
Start from any vertex and repeatedly absorb the cheapest reachable outsider. The partial result is always a single connected tree, unlike Kruskal's forest — the defining structural difference between the two algorithms.
Track the cheapest way in per vertex
key[v] holds the cost of the least expensive edge joining v to the current tree, starting at infinity for every vertex except the seed at 0. This one number per vertex is all the state the algorithm needs.
Absorb the minimum key each round
Select the unabsorbed vertex with the smallest key, add that key to the running total, and mark it in-tree. With a min-heap this selection is O(log V) rather than the O(V) of a linear scan.
Relax only the neighbours
After absorbing u, update key[v] = min(key[v], weight(u, v)) for each neighbour v still outside. Only edges crossing the boundary can matter — internal edges would create cycles and are never candidates.
Skip stale heap entries
A vertex can be pushed several times as its key improves. When popped, discard it if already absorbed — this lazy deletion is simpler than decrease-key and costs only a slightly larger heap.
Understand why greedy is safe
The cut property says the lightest edge crossing any partition belongs to some MST. The tree-versus-rest split is such a partition and the minimum key is that lightest edge, so no absorbed edge can be a mistake.
Compare with Kruskal's
Prim's is O(E log V) with a heap and suits dense graphs, especially at O(V²) with an adjacency matrix and no heap. Kruskal's sorts all edges at O(E log E) and suits sparse ones. The choice is about edge density, not correctness.
Solution & live demo
Common pitfalls
Not skipping vertices already in the tree
w, u = heapq.heappop(pq) in_tree[u] = True total += w
w, u = heapq.heappop(pq)
if in_tree[u]:
continueThe heap accumulates several stale entries per vertex, one for each frontier edge reaching it. Without the skip, a vertex is absorbed multiple times and the total is inflated by edges that form cycles.
Adding only one direction for undirected edges
adj[u].append((w, v))
adj[u].append((w, v)) adj[v].append((w, u))
An undirected edge must be traversable from both endpoints. Storing one direction makes parts of the graph unreachable from the start vertex and produces a spanning forest fragment rather than a full MST.
Pushing the vertex before the weight
heapq.heappush(pq, (v, w2))
heapq.heappush(pq, (w2, v))
A heap of tuples orders by the first element, so this pops the lowest-numbered vertex instead of the cheapest edge — turning Prim into an arbitrary traversal that returns a spanning tree of no particular weight.
Edge cases
No MST exists; the loop stops early with fewer than V−1 edges.
Ties can be broken arbitrarily — multiple MSTs of identical total weight.
Prim's with a heap is usually preferred over Kruskal's when E ≈ V².