EXM.1.AHL.TZ0.40
The weights of the edges of a complete graph G are shown in the following table.
Starting at B, use Prim’s algorithm to find and draw a minimum spanning tree for G. Your solution should indicate the order in which the vertices are added. State the total weight of your tree.
Markscheme / solution
Different notations may be used but the edges should be added in the following order.
Using Prim’s Algorithm, (M1)
BD A1
DF A1
FA A1
FE A1
EC A1
A2
Total weight = 12 A2
[10 marks]
Examiners’ report
[N/A]