Application Problems (20 points, 10 point each)

1. (1) List of edge weights in Kruskals algorithm:

(2) List of edge weights in Prims algorithm:

(3) Corresponding MST:

2.

Iteration 1	Iteration 2	Iteration 3	Iteration 4
{A} 36, 1, 15, ,,,, {B, C, D, E, F, G, H, I} AC, 1
Iteration 5	Iteration 6	Iteration 7	Iteration 8
{A, C, D, F, H} 34, 28, 41, 55 {B, E, G, I} ACDFHE, 1+11+8+5+3=28

vertex	A	C				E
distance	0	1				28

II. Application Problems (20 points, 10 point each) 1. Consider the following graph (numbers are edge weights): 10 2. (1) Give the list of edge weights in the MST in the order that Kruskal's algorithm inserts them. (2) Give the list of edge weights in the MST in the order that Prim's algorithm inserts them, assuming that it starts at the black vertex. (3) Draw the corresponding MST. 1 2. Using Dijkstra's algorithm on the weighted digraph below, calculate the shortest distance from vertex A to other vertices. 14 36 13 33 12 1 31 16 m 11 9 15 10 30 I 8 5