5.
| \(M\) | \(A\) | \(B\) | \(C\) | \(D\) | \(E\) |
| \(M\) | - | 215 | 170 | 290 | 210 | 305 |
| \(A\) | 215 | - | 275 | 100 | 217 | 214 |
| \(B\) | 170 | 275 | - | 267 | 230 | 200 |
| \(C\) | 290 | 100 | 267 | - | 180 | 220 |
| \(D\) | 210 | 217 | 230 | 180 | - | 245 |
| \(E\) | 305 | 214 | 200 | 220 | 245 | - |
The table shows the cost, in pounds, of linking five automatic alarm sensors, \(A , B , C , D\) and \(E\), and the main reception, \(M\).
- Use Prim's algorithm, starting from \(M\), to find a minimum spanning tree for this table of costs. You must list the arcs that form your tree in the order that they are selected.
- Draw your tree using the vertices given in Diagram 1 in the answer book.
- Find the total weight of your tree.
- Explain why it is not necessary to check for cycles when using Prim's algorithm.