MST & Prim's Algorithm (Detailed)

MST Definition

Connected, undirected, weighted $G(V,E,w)$. Spanning tree $T$ with $V-1$ edges spanning all vertices. MST minimizes $\sum_{e\in T} w(e)$.

Prim's Algorithm (as in Q94)

Prim(G, r):
  key[v]=∞, parent[v]=NIL, inQueue[v]=true for all v
  key[r]=0; Q = min-heap on key
  while Q≠∅:
    u=Extract-Min(Q); inQueue[u]=false
    for v in Adj[u]:
      if inQueue[v] and w(u,v)<key[v]:
        parent[v]=u; key[v]=w(u,v); Decrease-Key(Q,v,key[v])

Cut property ensures each added edge is safe.

Example Run (Graph: V=4 edges AB1 AC4 BC2 BD5 CD3)

Start A: key[A]=0

• Extract A → relax B1, C4 → key[B]=1 parent A, key[C]=4
• Extract B (min1) → relax C via2 <4 → key[C]=2 parent B; D via5 → key[D]=5
• Extract C (2) → relax D via3 <5 → key[D]=3 parent C
• Extract D (3) → done. MST edges: AB1, BC2, CD3 weight 6.

Complexity: $O(E\log V)$ binary heap, $O(V^2)$ array, $O(E+V\log V)$ Fibonacci.

When to Use Prim vs Kruskal

• Prim vertex-growth → dense graphs ($O(V^2)$ without heap good).
• Kruskal edge-sort → sparse graphs ($O(E\log E)$). Both $O(E\log V)$ order-wise.