Prim's Algorithm

Summarized notes on Introduction to Algorithms, Chapter 23

• edges in set $A$ always maintain a tree
• start from arbitrary root vertex $r$ and grow until tree spans all vertices in $V$
• during algorithm vertices not in $A$ are in min-priority queue ordered by edge weight
  • after algorithm finishes queue is empty
• maintains 3 loop invariants
  1. $A=\{(v,v.\pi ):v\in V-\{r\}-Q\}$   ($r$ is root)
  2. vertices in MST are those in $V-Q$
  3. for all vertices in $Q$, if $v.\pi \ne \text{NIL}$ then $v.key<\mathrm{\infty }$ and $v.key$ is weight of a light edge connecting $v$ to some vertex already in MST

Example

Complexity

Running time
$(E\lg V)$	Prim's using binary min-heap
$(E+V\lg V)$	Prim's using Fibonacci heap