1. Given the following edge-weighted graph:
6 15
0-1 1.3
0-2 5.2
0-3 2.1
0-4 6.8
0-5 3.5
1-2 5.6
1-3 2.0
1-4 6.9
1-5 3.6
2-3 5.7
2-4 6.1
2-5 6.0
3-4 7.0
3-5 5.1
4-5 7.8
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) As Prim's algorithm executes, how many elements of each of the edgeTo[] and
distTo[] arrays must be updated each time an edge is added to the MST? [1]
f) Which of the two algorithms is a better choice for computing the MST for
this graph? Why? [2]
2. Given the following edge-weighted graph:
6 8
0-1 4.1
0-2 4.5
1-2 2.1
2-3 3.5
2-4 4.8
2-5 2.4
3-4 3.9
4-5 3.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]
