2. Prim's algorithm finds a minimum spanning tree for a connected graph.
- Explain the terms
- connected graph,
- tree,
- spanning tree.
- Name an alternative algorithm for finding a minimum spanning tree.
\begin{table}[h]
| Cambridge | London | Norwich | Oxford | Portsmouth | Salisbury | York |
| Cambridge (C) | - | 60 | 62 | 81 | 132 | 139 | 156 |
| London (L) | 60 | - | 116 | 56 | 74 | 88 | 211 |
| Norwich (N) | 62 | 116 | - | 144 | 204 | 201 | 181 |
| Oxford (O) | 81 | 56 | 144 | - | 84 | 63 | 184 |
| Portsmouth (P) | 132 | 74 | 204 | 84 | - | 43 | 269 |
| Salisbury (S) | 139 | 88 | 201 | 63 | 43 | - | 248 |
| York (Y) | 156 | 211 | 181 | 184 | 269 | 248 | - |
\captionsetup{labelformat=empty}
\caption{Figure 2}
- Use Prim's algorithm, starting at London, to find the minimum spanning tree for these cities. You must clearly state the order in which you selected the edges of your tree, and the weight of the final tree.
- Draw your tree using the vertices given in Diagram 2 in the answer book.
(5)