Chapter 23 Answers

Question 23.1 - Complete the table for MST-Kruskal (G, w)

Set-Of-Edges MST-Kruskal (G, w) --  pre: G is a connected graph --  post: result = MST of G   -- Initialization   1 A ← |   2 for each vertex v ∈ V[G] do O(|V|) 3    Make-Set (v) O(1) 4 Sort the edges of E, taken in nondecreasing order by weight w O(E lg E)   -- Perform MST algorithm   5 for each edge (u, v) ∈ G.E, taken in nondecreasing order by weight do O(E lg E) 6    if Find-Set (u) ≠ Find-Set (v) then O(lg E) 7       A ← A U {(u, v)}   8       Union (u, v)   9 return A

Weight	edge	Find-Set (u) ≠ Find-Set (v)	A	Sets
1	(g,h)	safe	{(g,h)}	{g,h}
2	(c,i)	safe	{(g,h),(c,i)}	{g,h}    {c,i}
2	(f,g)	safe	{(g,h),(c,i),(f,g)}	{f,g,h}  {c,i}
4	(a,b)	safe	{(g,h),(c,i),(f,g),(a,b)}	{a,b}   {f,g,h}  {c,i}
4	(c,f)	safe	{(g,h),(c,i),(f,g),(a,b),(c,f)}	{a,b}   {c,f,g,h,i}
6	(g,i)	reject
7	(c,d)	safe	{(g,h),(c,i),(f,g),(a,b),(c,f),(c,d)}	{a,b}   {c,d,f,g,h,i}
8	(a,h)	safe	{(g,h),(c,i),(f,g),(a,b),(c,f),(c,d),(a,h)}	{a,b,c,d,f,g,h,i}
8	(b,c)	reject
9	(d,e)	safe	{(g,h),(c,i),(f,g),(a,b),(c,f),(c,d),(a,h),(d,e)}	{a,b,c,d,e,f,g,h,i}
10	(e,f)	reject		Complete at |V| vertices
11	(b,h)	reject
14	(d,f)	reject

• A = {}
• V = {{a} {b} {c} {d} {e} {f} {g} {h} {i}}
• E (sorted edge list) = <((g,h), 1) ((c,i), 2) ((f,g), 2) ((a,b), 4) ((c, f), 4)
                                    ((g,i),  6) ((c,d), 7) ((h,i), 7) ((a,h), 8) ((b,c), 8)
                                    ((d,e), 9) ((e,f), 10) ((b,h), 11) ((d,f), 14) >

MST-Prim (G, w, r) --   pre: G is a connected graph --   post: A = {(v, v.π) : v ∈ G.V - {r}}   -- Initialization 1 for each vertex u ∈ G.V do 2    u.key ← ∞ 3    u.π ← NIL 4 Q ← G.V 5 r.key ← 0   -- Perform MST algorithm 6 while Q ≠ | do 7    u ← Extract-Min (Q) 8    for each v ∈ Adj[u] do 9       if v ∈ Q and w(u,v) < v.key then 10          v.π ← u 11          v.key ← w(u,v)

Question 23.2

The following lists the state of Q and vertices, v, through MST-PRIM while Q ≠ | do.

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

u	Q
	a:0:NIL	b:∞:NIL	c:∞:NIL	d:∞:NIL	e:∞:NIL	f:∞:NIL	g:∞:NIL	h:∞:NIL	i:∞:NIL
a	b:4:a	h:8:a	c:∞:NIL	d:∞:NIL	e:∞:NIL	f:∞:NIL	g:∞:NIL	i:∞:NIL
b	c:8:b	h:8:a	d:∞:NIL	e:∞:NIL	f:∞:NIL	g:∞:NIL	i:∞:NIL
c	i:2:c	f:4:c	d:7:c	h:8:a	e:∞:NIL	g:∞:NIL
i	f:4:c	g:6:i	d:7:c	h:7:i	e:∞:NIL
f	g:2:f	d:7:c	h:7:i	e:10:f
g	h:1:g	d:7:c	e:10:f
h	d:7:c	e:10:f
d	e:9:d
e

Complete the execution of MST-PRIM

Vertex	a	b	c	d	e	f	g	h	i
key	0	4	8	7	9	4	2	1	2
π	NIL	a	b	c	d	c	f	g	c