OCR A Level: Decision 1 - Prim's Algorithm [June 2007 Q6]

Computer Science Level pending

The table shows the distances, in miles, along the direct roads between six villages, $$A$$ to $$F$$. A dash ($$−$$) indicates that there is no direct road linking the villages.

$$(\text{i})$$ On the table in the insert, use Prim’s algorithm to find a minimum spanning tree. Start by crossing out row $$A$$. Show which entries in the table are chosen and indicate the order in which the rows are deleted. Draw your minimum spanning tree and state its total weight.

$$(\text{ii})$$ By deleting vertex $$B$$ and the arcs joined to vertex $$B$$, calculate a lower bound for the length of the shortest cycle through all the vertices.

$$(\text{iii})$$ Apply the nearest neighbour method to the table above, starting from $$F$$, to find a cycle that passes through every vertex and use this to write down an upper bound for the length of the shortest cycle through all the vertices.