# 23.2 Prim's Algorithm

Properties:

Starts at arbitrary root,

edges of set A ⊆ MST always form a single tree,

vertices in a min-heap by edge weight from a discovered vertex,

updates vertices in min-heap as lower weight connecting edge discovered,

greedy by extracting minimum weight edge to explore next,

by selecting minimum weight edge (u, v) ∉ A,

and ensuring cut respects A,

(u, v) is safe

A U {(u, v)} ⊆ MST.

Root a.

 u Q  Each vertex is unique in the queue keyed by its current minimum weight. a:0:NIL b:∞:NIL c:∞:NIL d:∞:NIL e:∞:NIL f:∞:NIL g:∞:NIL h:∞:NIL i:∞:NIL (a) (b) (c) (d) (e) (f) (g) (h) (i)
 MST-Prim (G, w, r) 1 for each vertex u ∈ G.V 2 u.key ← ∞ 3 u.Π ← NIL 4 Q ← G.V 5 r.key ← 0 6 while Q ≠ ∅ 7 u ← Extract-Min (Q) 8 for each v ∈ G.Adj[u] 9 if v ∈ Q and w(u, v) < v.key 10 v.Π ← u 11 v.key ← w(u,v)
 A a b c d e f g h i key 0 Π NIL

MST-Prim maintains a min-queue keyed by weight from the vertex connecting to the tree.

Queue entries can be represented as:

(v : v.key : v.Π) where (b : 4 : a)

is vertex b connects to the tree through predecessor vertex a with weight of 4.

MST-Prim (G, w, r)
--   pre: G is a connected graph
--           w is edge weights
--           r is root
--   post: A = {(v, v.Π) : v ∈ G.V - {r}}
 1 for each vertex u ∈ G.V 2 u.key ← ∞ 3 u.Π ← NIL 4 Q ← G.V -- Q is a min-heap 5 r.key ← 0 -- Update r in min-heap 6 while Q ≠ ∅ 7 u ← Extract-Min (Q) 8 for each v ∈ G.Adj[ u ] 9 if v ∈ Q and w(u, v) < v.key --  v ∈ Q implies u and v in different components 10 v.Π ← u 11 v.key ← w(u, v) -- Updates min-heap

After six iterations of while Q do the queue below and the vertices have been updated to reflect vertices added to the tree rooted at vertex a.

 u Q  Each vertex is unique in the queue keyed by its current minimum weight. a:0:NIL b:∞:NIL c:∞:NIL d:∞:NIL e:∞:NIL f:∞:NIL g:∞:NIL h:∞:NIL i:∞:NIL (a) a b:4:a h:8:a c:∞:NIL d:∞:NIL e:∞:NIL f:∞:NIL g:∞:NIL i:∞:NIL (b) b c:8:b h:8:a d:∞:NIL e:∞:NIL f:∞:NIL g:∞:NIL i:∞:NIL (c) c i:2:c f:4:c d:7:c h:8:a e:∞:NIL g:∞:NIL (d) i f:4:c g:6:i d:7:c h:7:i e:∞:NIL (e) f g:2:i d:7:c h:7:i e:10:f (f) g h:1:g d:7:c e:10:f (g) (h) (i)

Final values for A.

 A a b c d e f g h i key 0 4 8 7 10 4 2 1 2 Π NIL a b c f c f g c

 MST-Prim (G, w, r) 1 for each vertex u ∈ G.V 2 u.key ← ∞ 3 u.Π ← NIL 4 Q ← G.V 5 r.key ← 0 6 while Q ≠ ∅ 7 u ← Extract-Min (Q) 8 for each v ∈ G.Adj[u] 9 if v ∈ Q and w(u, v) < v.key 10 v.Π ← u 11 v.key ← w(u,v)

Note that A = {(v, v.Π) : v ∈ G.V - {r}}

Safe edge:

Line 7 ensures the minimum edge explored first (light edge),

(c, i) is minimum edge crossing cut (S, V − S)

Line 9  if v ∈ Q ensures cut respects A since v ∈ Q (u ← Extract-Min (Q) so u ∉ Q) implies no u such that (u, v) ∈ A,

i ∈ Q = V-S and cut (S, V − S) does not cross A, adding edge (c, i) to A would not form a circuit.

Question 23.2

The following lists the state of Q and vertices, v, prior to MST-Prim while Q

Q min-priority queue of values v : v.key : v.Π

Complete the next four steps in the execution of MST-Prim

 u Q  Each vertex is unique in the queue keyed by its current minimum weight. a:0:NIL b:∞:NIL c:∞:NIL d:∞:NIL e:∞:NIL f:∞:NIL g:∞:NIL h:∞:NIL i:∞:NIL (a) (b) (c) (d)

 A a b c d e f g h i key 0 ∞ ∞ ∞ ∞ ∞ ∞ 8 ∞ Π NIL NIL NIL NIL NIL NIL NIL a NIL
 MST-Prim (G, w, r) 1 for each vertex u ∈ G.V 2 u.key ← ∞ 3 u.Π ← NIL 4 Q ← G.V 5 r.key ← 0 6 while Q ≠ ∅ 7 u ← Extract-Min (Q) 8 for each v ∈ G.Adj[u] 9 if v ∈ Q and w(u, v) < v.key 10 v.Π ← u 11 v.key ← w(u,v)

Analysis - O(|V| lg |V|)

Line 4 - Build-Min-Heap is O(|V|) implemented as a binary (max of two children) min-heap.

Recall the height of most nodes is small since most are at the bottom.

Line 7 - Extract-Min is O(lg |V|)

Line 8 - |V| vertices + |E| edges, all vertices must be in MST

Line 9 - Set membership, v ∈ Q, is O(1) using bit operations

Line 11 - Decrease-Key, when lower weight path discovered, is O(lg |V|)

 MST-Prim (G, w, r) --   pre: G is a connected graph --           w is edge weights --           r is root--   post: A = {(v, v.Π) : v ∈ G.V - {r}} 1 for each vertex u ∈ G.V O(|V|) 2 u.key ← ∞ 3 u.Π ← NIL 4 Q ← G.V                           -- Q is a min-heap O(|V|) 5 r.key ← 0                         -- Update r in min-heap 6 while Q ≠ ∅ O(|V|) 7 u ← Extract-Min (Q) O(|V| lg |V|) 8 for each v ∈ G.Adj[ u ] O(|V|+|E|) 9 if v ∈ Q and w(u, v) < v.key O(|V|+|E|) 10 v.Π ← u 11 v.key ← w(u, v)      -- Updates min-heap O((|V|+|E|)lg |V|)