Given the following edge$-$weighted graph:

$6,$

$0-1,4\mathrm{.}1$

$0-2,4\mathrm{.}5$

$1-2,2\mathrm{.}1$

$2-3,3\mathrm{.}5$

$2-4,4\mathrm{.}8$

$2-5,2\mathrm{.}4$

$3-4,3\mathrm{.}9$

$4-5,3\mathrm{.}7$

a$)$ Show a trace of the execution of Kruskal's Algorithm on this graph.

Your trace should be in the style of the trace shown on page $624$ of

the text. $[5]$

b$)$ How many elements are inserted into the priority queue used by Kruskal's

algorithm when computing the MST for this graph? $[1]$

c$)$ How many elements of the priority queue do you consume before the algorithm

completes computing the MST$?[1]$

d$)$ Show a trace of the execution of the eager version of Prim's Algorithm on

this graph. Your trace should be in the style of the trace shown on page

$621$ of the text. $[5]$

e$)$ Contrast the amount of work Prim's algorithm has to do for this graph and

the graph in the previous question when updating the edgeTo and distTo

arrays. $[1]$

f$)$ Which of the two algorithms is a better choice for computing the MST for

this graph? Why? $[2]$