23.2 Prim's Algorithm

Document last modified: 

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.

 

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 uG.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 vG.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.keyw(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 uG.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 vG.Adj[u]
9       if v ∈ Q and w(u, v) < v.key
10          v.Π ← u
11          v.keyw(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 three 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)                    

 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 uG.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 vG.Adj[u]
9       if v ∈ Q and w(u, v) < v.key
10          v.Π ← u
11          v.keyw(u,v)


 

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

Line 4 - Build-Min-Heap is O(|V|) implemented as a binary 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 

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 uG.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 vG.Adj[ u ] O(|V|+|E|)
9       if v ∈ Q and w(u, v) < v.key O(|V|+|E|)
10          v.Π ← u  
11          v.keyw(u, v)      -- Updates min-heap O((|V|+|E|)lg |V|)
or O(|V| lg |V|)