CSC403: Written Homework: Minimum Spanning Trees

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]