Skip to content

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 \neq \text{NIL}\) then \(v.key < \infty\) and \(v.key\) is weight of a light edge connecting \(v\) to some vertex already in MST

Example

img

Complexity

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