Question $1(30$ marks$)$

Consider the following graph:

$($a$)$ Run Krukal's minimum spanning tree algorithm on the graph. Use the following table with

three columns to represent your answers. The first column is the step number. The second

column is the edge chosen. The third column is the weight of the edge chosen. You are

required to use the following table as the template.

Step Edge Weight

$..........$

$.........$

$($b$)$ Run Prim's minimum spanning tree algorithm on the same graph. Use the following table with

three columns to represent your anowers. The first column is the step number. The second

column is the edge chosen. The third column is the weight of the edge chosen. You are

required to use the following table as the template.

Step Edge Weight

$..........$

$.........$

$($c$)$ Run Dijkstra's algorithm on the same graph to compute the shortest path from a to f$,$ using the

following table as the template. The first columm is the step number. The second column is the

edge chosen. The third column is the vertex chosen. The fourth column is the weight of the

shortest path from the starting vertex to the chosen vertex

Furthermore, write down the shortest path you obtain AND its weight.

Step Edge Weight Path Weight

$.............$

$............$