4. (a) State three differences between Prim's algorithm and Kruskal's algorithm for finding a minimum spanning tree.
(3)
\begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{4609ffb5-d270-4ff3-aa44-af8442a38b66-5_864_1073_386_497}
\captionsetup{labelformat=empty}
\caption{Figure 4}
\end{figure}
[The total weight of the network is 341]
(b) Use Prim's algorithm, starting at D , to find a minimum spanning tree for the network shown in Figure 4. You must list the arcs in the order in which you select them.
(3)
Figure 4 models a network of school corridors. The number on each arc represents the length, in metres, of that corridor. The school caretaker needs to inspect each corridor in the school to check that the fire alarms are working correctly. He wants to find a route of minimum length that traverses each corridor at least once and starts and finishes at his office, D.
(c) Use the route inspection algorithm to find the corridors that will need to be traversed twice. You must make your method and working clear.
The caretaker now decides to start his inspection at G. His route must still traverse each corridor at least once but he does not need to finish at G.
(d) Determine the finishing point so that the length of his route is minimised. You must give reasons for your answer and state the length of his route.
(3)