• Macquarie Home »
• Faculty of Science »
• Computing »
• Undergraduate »
• Unit List

Week 11

1. Construct the DFS spanning tree starting from vertex A.
2. Construct the BFS spanning tree starting from vertex A.
3. (*)Construct a minimum spanning tree using Prim's algorithm. Start from vertex A. For submission you may just submit the final MST but you should be able to trace through the algorithm.
4. (*)Construct a minimum spanning tree using Kruskal's algorithm. For submission you may just submit the final MST but you should be able to trace through the algorithm.

   Considering the above graph:

5. (*) Trace through Dijkstra's single-source shortest path algorithm on the above graph, starting from vertex a. Show the vertex set and weight array at each step. Wherever there is a choice of vertex you should choose the smallest alphabetically.
   Show the full working for submission here i.e. weight array and vertex Set at each step.
6. State the loop invariant of Dijkstra's algorithm.
7. Discuss the efficiency of Dijkstra's shortest path algorithm.
8. Now repeat Dijkstra's algorithm starting from D.