23.2 Prim's Algorithm

Document last modified:

Has 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, (u, v) is safe, A | {(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

10      v.π ← u

11          v.key ← w(u, v)      -- Updates min-heap

After four 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

A	a	b	c	d	e	f	g	h	i
key	0	4	8	∞	∞	∞	∞	∞	2
π	NIL	a	b	NIL	NIL	NIL	NIL	NIL	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}}

Question 23.2

The following lists the state of Q and vertices, v, after four steps through MST-Prim while Q ≠ |

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

Complete 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

(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

A a b c d e f g h i

key 0 4 8 ∞ ∞ ∞ ∞ ∞ 2

π NIL a b NIL NIL NIL NIL NIL c

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

Line 4 - Build-Min-Heap is O(n)

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|)