Prim's Algorithm Theory

Problem

Given a connected, undirected, weighted graph G, construct a spanning tree of minimum total weight. If the graph is disconnected, Prim's run from one start vertex builds an MST for that component only (can repeat to get a minimum spanning forest).

Greedy Strategy & Cut Property

• Maintain a partition (Tree set T, Remaining set V−T).
• At each step choose the lightest edge crossing the cut (T, V−T).
• Cut Property guarantees this edge is safe (belongs to some MST).
• Prim operationalizes this locally (frontier edges only) vs Kruskal's global ordering.

Data Structures

• key[v]: Weight of best edge connecting v to current tree (∞ if none).
• parent[v]: Predecessor forming chosen MST edge.
• PQ: Min-priority queue keyed by key[v] (supports decrease-key).
• inMST set: Vertices already fixed (frontier boundary maintained implicitly by keys).

Pseudocode

1PRIM(G=(V,E), w, start):
2  for each v in V:
3    key[v] = +∞
4    parent[v] = NIL
5  key[start] = 0
6  PQ = min-priority-queue keyed by key[]
7  insert all vertices into PQ
8  inMST = ∅
9  while PQ not empty:
10    u = extract-min(PQ)
11    add u to inMST
12    if parent[u] ≠ NIL: add edge (parent[u], u) to MST
13    for each (u,v) in Adj[u]:
14      if v ∉ inMST and w(u,v) < key[v]:
15        key[v] = w(u,v)
16        parent[v] = u
17        decrease-key(PQ, v)
18  return MST

Complexity

Decrease-key operations dominate with heaps. For dense graphs (m ≈ n^2) the simple O(n^2) implementation is practical and often faster in practice.

Correctness Sketch

• Invariant: key[v] always equals lightest crossing edge weight for v (if any explored).
• Extracted vertex u has minimal key among V−T; its incident chosen edge is safe by cut property.
• After n−1 extractions (or PQ empty) the accumulated edges form an MST (or forest component).

Edge Cases

• Disconnected: Need to restart from unvisited vertex to cover all components.
• Negative Weights: Supported (no cycles added; minimal crossing edge logic unaffected).
• Parallel Edges: Best one influences key updates naturally.
• Self-loops: Ignored (never connect new vertex).