CS300-Homework 5 Solved

Question 1



Starting from G, trace the operations of the Dijkstra’s weighted shortest path algorithm on the graph given in Figure 1.

Question 2



Starting from G, trace the operations of the Prim’s minimum spanning tree algorithm on the graph given in Figure 1.

Question 3



Trace the operations of Kruskal’s minimum spanning tree algorithm on the graph given in Figure 1.

Question 4



Starting from S, trace the operations of breadth-first traversal on the graph given in Figure 2.



Figure 2: A directed weighted graph.

Question 5



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