GeeksforGeeks Medium

MST — Prim's Algorithm

Build a minimum spanning tree by growing one tree outward from a start vertex.

graphmstgreedyheap

02

Intuition

Keep one connected tree and repeatedly absorb whichever outside vertex is cheapest to attach. Each vertex remembers key[v] — the cost of the cheapest single edge joining it to the current tree. The cut property guarantees this is safe: the lightest edge crossing the boundary between tree and non-tree always belongs to some MST.

How to spot this pattern

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.

03

Approach

1

Track the cheapest way in

key[v] starts ∞ (0 for the seed). Repeatedly pick the unabsorbed vertex with the smallest key, add that cost to the total, and mark it in-tree.

2

Update the frontier

After absorbing u, each neighbour v outside the tree may now have a cheaper entry: key[v] = min(key[v], w(u, v)). Only edges crossing the cut matter.

3

Why greedy is optimal

The cut property: for any split of the vertices, the lightest crossing edge is in some MST. Every step takes exactly such an edge, so the final tree is minimal.

04

Solution & live demo

▶1import heapq
▶2 
▶3def prim(n, edges):
▶4    adj = [[] for _ in range(n)]
▶5    for u, v, w in edges:         # undirected: both directions
▶6        adj[u].append((w, v))
▶7        adj[v].append((w, u))
▶8    in_tree = [False] * n
▶9    pq = [(0, 0)]                 # (cost, vertex)
▶10    total = 0
▶11    while pq:
▶12        w, u = heapq.heappop(pq)
▶13        if in_tree[u]:
▶14            continue
▶15        in_tree[u] = True         # absorb the cheapest reachable vertex
▶16        total += w
▶17        for w2, v in adj[u]:
▶18            if not in_tree[v]:
▶19                heapq.heappush(pq, (w2, v))
▶20    return total

05

Common pitfalls

Not skipping vertices already in the tree

✗ Wrong

w, u = heapq.heappop(pq)
in_tree[u] = True
total += w

✓ Right

w, u = heapq.heappop(pq)
if in_tree[u]:
    continue

The 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

✗ Wrong

adj[u].append((w, v))

✓ Right

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

✗ Wrong

heapq.heappush(pq, (v, w2))

✓ Right

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.

06

Edge cases

Disconnected graph

No MST exists; the loop stops early with fewer than V−1 edges.

Equal weights

Ties can be broken arbitrarily — multiple MSTs of identical total weight.

Dense graphs

Prim's with a heap is usually preferred over Kruskal's when E ≈ V².

07

Complexity

Time

O(E log V)

Space

O(V + E)

Heap holds candidate crossing edges.