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.

 

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.

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 implies no u such that (u, v) ∈ A,

i ∈ Q, (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, after two steps through MST-Prim while Q ≠ ∅

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

Complete the next two 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)	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

A	a	b	c	d	e	f	g	h	i
key	0	4	8	∞	∞	∞	∞	8	∞
Π	NIL	a	b	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 min-heap.

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 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|) or O(|V| lg |V|)