D1 June 2008 Q4

(a) State two differences between Kruskal’s algorithm and Prim’s algorithm for finding a minimum spanning tree. (2)

(b) Listing the arcs in the order that you consider them, find a minimum spanning tree for the network in Figure 4, using

(i) Prim’s algorithm,

(ii) Kruskal’s algorithm. (6)

Mark scheme (a)

Scheme	Marks
e.g. Prims starts with any vertex, Kruskal starts with the shortest arc. It is not necessary to check for cycles when using Prim. Prims adds nodes to the growing tree, Kruskal adds arcs. The tree ‘grows’ in a connected fashion when using Prim. Prim can be used when data in a matrix form. Other correct statements also get credit.	B2, 1, 0
	(2)

(a) 1B1: Generous one correct difference. If bod give B1

2B1: Generous two distinct, correct differences.

Scheme	Marks
(i) e.g. AC, CF, FD, DE, DG, AB.	M1, A1, A1
	(3)
(ii) CF, DE, DF, not CD, not EF, DG, not FG, not EG, AC, not AD, AB. [18, 19, 20, not 21, not 21 , 22 , not 23, not 24, 25, not 26, 27]	M1, A1, A1
	(3)
	(8 marks)