Prim's Algorithm & Time Complexity

Algorithm (Greedy MST)

Prim(G, s):
  for v in V: key[v]=∞, parent[v]=NIL, inMST[v]=false
  key[s]=0
  Q = min-priority queue of V keyed by key
  while Q not empty:
    u = Extract-Min(Q); inMST[u]=true
    for each v in Adj[u]:
      if !inMST[v] and w(u,v) < key[v]:
        parent[v]=u; key[v]=w(u,v); Decrease-Key(Q,v,key[v])

Growth from source $s$, repeatedly adds minimum-weight edge crossing cut $(MST, V-MST)$ (cut property guarantees safety). Result = MST with $V-1$ edges, parent pointers form tree.

Example (as in Q89): start A, edges AB1 etc → picks AB1, then CD2 etc until MST weight minimal.

Correctness Sketch

Cut property: lightest edge crossing any cut belongs to some MST. Prim's cut is (inMST, rest); picking min crossing edge maintains invariant that inMST vertices are connected by MST edges.

Time Complexity

Depends on priority queue:

• Adjacency list + binary heap: $O((V+E)\log V)$ = $O(E\log V)$ (extract-min $V$ times, decrease-key up to $E$ times).
• Adjacency list + Fibonacci heap: $O(E + V\log V)$ (amortized decrease-key $O(1)$).
• Adjacency matrix + array (no heap, scan min): $O(V^2)$ — best for dense graphs ($E≈V^2$).
• Adjacency matrix + binary heap: still $O(E\log V)$.

Space: $O(V+E)$ or $O(V^2)$ for matrix.

Comparison

Prim good for dense graphs (array $O(V^2)$), Kruskal $O(E\log E)$ better for sparse. Both optimal greedy MST algorithms.