EXM.1.AHL.TZ0.36
Apply Prim’s algorithm to the weighted graph given below to obtain the minimal spanning tree starting with the vertex A.
Find the weight of the minimal spanning tree.
Markscheme / solution
We start with point A and write S as the set of vertices and T as the set of edges.
The weights on each edge will be used in applying Prim’s algorithm.
Initially, S = {A}, T = Φ. In each subsequent stage, we shall update S and T.
Step 1: Add edge h: So S = {A, D}, T = {h}
Step 2: Add edge e: So S = {A, D, E} T = {h, e}
Step 3: Add edge d: Then S = {A, D, E, F} T = {h, e, d}
Step 4: Add edge a: Then S = {A, D, E, F, B} T = {h, e, d, a}
Step 5: Add edge i: Then S = {A, D, E, F, B, G} T = {h, e, d, a, i}
Step 6: Add edge g: Then S = (A, D, E, F, B, G, C} T = {h, e, d, a, I, g} (M4)(A3)
Notes: Award (M4)(A3) for all 6 correct,
(M4)(A2) for 5 correct;
(M3)(A2) for 4 correct,
(M3)(A1) for 3 correct;
(M1)(A1) for 2 correct,
(M1)(AO) for 1 correct
OR
(M2) for the correct definition of Prim’s algorithm,
(M2) for the correct application of Prim’s algorithm,
(A3) for the correct answers at the last three stages.
Now S has all the vertices and the minimal spanning tree is obtained.
The weight of the edges in T is 5 + 3 + 5 + 7 + 5 + 6
= 31 (A1)
[8 marks]