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.

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

python

▶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

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².

06

Complexity

Time

O(E log V)

Space

O(V + E)

Heap holds candidate crossing edges.