(a-b)
III. h is closest, add h, update
1->g, 7->i
(a, b, h)(c-8,
g-1, i-7)
(a-b,a-h)
IV. g closest, add g, update 2->f,
6->i
(a, b, h, g)(f-2,
i-6,c-8)
(a-b,a-h,h-g)
V. f closest, add f, update 4->c,
14->d,10->e
(a,b,h,g,f)(c-4,i-6,d-14,e-10)
(a-b,a-h,h-g,g-f)
VI c closest, add c, update 2->i,
7->d
(a,b,h,g,f,c)(i-2,
d-7, e-10)
(a-b,a-h, h-g,g-f,f-c)
VII i closest, add i, update none
(a,b,h,g,f,c,i)(d-7,e-10)
(a-b,a-h, h-g,g-f,f-c,
c-i)
VII d closest, add d, update 9->e
(a,b,h,g,f,c,i,d)
(e-9)
(a-b,a-h, h-g,g-f,f-c,
c-i,c-d)
IX add e
(a,b,h,g,f,c,i,d,e)
() done
(a-b,a-h, h-g,g-f,f-c,
c-i,c-d,d-e)
1.b)
Cost = 4 + 8 + 1 + 2 + 4 + 2 + 7
+ 9 = 37
Tree:
a---b
i
|
|
h---g---f---c---d----e
2.a)
sort all edges
( g-h:1, c-i:2, f-g:2, a-b:4, c-f:4,
g-i:6,
c-d:7, a-h:8, b-c:8, d-e:9,
b-h:11,d-f:14)
I. (g-h) added
II. (c-i) added
III. (f-g) added
IV. (a-b) added
V. (c-f) added
VI. (g-i) rejected (cycle)
VII. (c-d) added
VIII (a-h) added
IX (b-c) rejected ( cycle )
X. (d-e) added
Done
b) cost = 37
Tree:
a---b
i
|
|
h---g---f---c---d----e