Homework 22

Details

Consider the following graph

1. (8) Use Prim's algorithm to find a minimum spanning tree for the graph.
   • Assume the adjacency lists are stored in numerical order and start from vertex 0.
   • Give the value in the priority queue at every step of the algorithm (Look at Example 9.101).
   • Draw the graph and darken the edges of the minimum spanning tree. (you may scan/photocopy that page from the book if you wish).
   • Finally, give the weight of the minimum spanning tree.
2. (8) Use Kruskal's algorithm to find a minimum spanning tree for the graph.
   • Clearly label the vertices with the order they are visited.
   • Clearly darken the edges of the minimum spanning tree. (you may scan/photocopy that page from the book if you wish).
   • Finally, give the weight of the minimum spanning tree.