CS 300 Homework 5 Solved 

Description

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,

1. Trace the operations of depth-first traversal.
2. Give the post-order numbers for all the nodes.
3. Give the pre-order numbers for all the nodes.
4. List the tree arcs, cross arcs, forward arcs, and backward arcs.

Question 6 

Find a topological ordering of the graph given in Figure 3.

Figure 3: An example DAG