Description
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 breadth-first 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,
a) Trace the operations of depth-first traversal.
b) Give the post-order numbers for all the nodes.
c) Give the pre-order numbers for all the nodes.
d) 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
