Description
Figure 1: A directed weighted graph.
Question 1 (20 points)
Starting from G, trace the operations of the Dijkstra’s weighted shortest path algorithm on the graph given in Figure 1.
Question 2 (15 points)
Starting from G, trace the operations of the Prim’s minimum spanning tree algorithm on the graph given in Figure 1.
Question 3 (15 points)
Trace the operations of Kruskal’s minimum spanning tree algorithm on the graph given in Figure 1.
Question 4 (15 points)
Starting from S, trace the operations of breadthfirst traversal on the graph given in Figure 2.
2
Figure 2: A directed weighted graph.
Question 5 (20 points)
Given Figure 2 and starting from S,

Trace the operations of depthfirst traversal.

Give the postorder numbers for all the nodes.

Give the preorder numbers for all the nodes.

List the tree arcs, cross arcs, forward arcs, and backward arcs.
Question 6 (15 points)
Find a topological ordering of the graph given in Figure 3.
3
Figure 3: An example DAG.
4