Description
1. Execute Prim’s minimum spanning tree algorithm by hand on the graph below showing
how the data structures evolve specifically indicating when the distance from a fringe
vertex to the tree is updated. Clearly indicate which edges become part of the minimum
spanning tree and in which order. Start at vertex A.
A B G
F I H C
E D
2
2 2
2 1
1 3 3 4
5 4 6
6 7
8
2. Execute Kruskal’s algorithm on the weighted tree shown below. Assume that edges of
equal weight will be in the priority queue in alphabetical order. Clearly show what
happens each time an edge is removed from the priority queue and how the dynamic
equivalence relation changes on each step and show the final minimum spanning tree that
is generated.
3. Give an example of a weighted graph for which the minimum spanning tree is unique.
Indicate what the minimum spanning tree is for that graph. Give another example of a
weighted graph that has more than one minimum spanning tree. Show two different
minimum spanning trees for that graph. What determines whether a graph has more than
one minimum spanning tree?
4. Given the following adjacency lists (with edge weights in parentheses) for a directed
graph:
A: B(5), C(3), D(1)
B: C(1), D(3)
C: B(3), D(7), E(1)
D: A(6), C(3)
E: F(5)
F: D(3), A(4)
Execute Dijkstra’s shortest-path algorithm by hand on this graph, showing how the data
structures evolve, with A as the starting vertex. Clearly indicate which edges become part
of the shortest path and in which order.
Grading Rubric
Problem Meets Does Not Meet
Problem 1
10 points 0 points
Indicated when the distance from a
fringe vertex to the tree was updated
(3)
Did not indicate when the distance
from a fringe vertex to the tree was
updated (0)
Indicated which edges became part of
the minimum spanning tree and in
which order (3)
Did not indicate which edges became
part of the minimum spanning tree and
in which order (0)
Provided the correct final minimum
spanning tree (4)
Did not provide the correct final
minimum spanning tree (0)
Problem 2
10 points 0 points
Showed what happened each time an
edge was removed from the priority
queue (3)
Did not show what happened each
time an edge was removed from the
priority queue (0)
Showed how the dynamic equivalence
relation changed on each step (3)
Did not show how the dynamic
equivalence relation changed on each
step (0)
Provided the correct final minimum
spanning tree (4)
Did not provide the correct final
minimum spanning tree (0)
Problem 3
10 points 0 points
Provided a correct example of a
weighted graph for which the
minimum spanning tree is unique (2)
Did not provide a correct example of a
weighted graph for which the
minimum spanning tree is unique (0)
Provided the correct unique minimum
spanning tree for that graph (2)
Did not provide the correct unique
minimum spanning tree for that graph
(0)
Provided a correct example of a
weighted graph that has more than
one minimum spanning tree (2)
Did not provide a correct example of a
weighted graph that has more than
one minimum spanning tree (0)
Provided two correct distinct minimum
spanning trees for that graph (2)
Did not provide two correct distinct
minimum spanning trees for that graph
(0)
Correctly explained what determines
whether a graph has more than one
minimum spanning tree (2)
Did not correctly explain what
determines whether a graph has more
than one minimum spanning tree (0)
Problem 4
10 points 0 points
Clearly indicated which edges became
part of the shortest path and in which
order (5)
Did not clearly indicate which edges
became part of the shortest path and
in which order (0)
Provided correct final shortest path
tree (5)
Did not provide correct final shortest
path tree (0)
