Minimum Spanning Tree (a) There is a weighted undirected graph in Fig. 5. There
ID: 3812699 • Letter: M
Question
Minimum Spanning Tree (a) There is a weighted undirected graph in Fig. 5. There are six nodes, A, B, C, D, E, and F. The value beside each edge is its weight. Now you are executing the Kruskal algorithm to compute the minimum spanning tree on this graph. Instead of drawing the tree, all you need to do is to list the edges in the resulting MST, in the order of the time they are added to the MST. (b) There is a weighted undirected graph in Fig. 6. There are six nodes, A, B, C, D, E, and F. The value beside each edge is its weight. Now you are executing the Prim algorithm to compute the minimum spanning tree on this graph, starting with vertex A. Instead of drawing the tree, all you need to do is to list the edges in the resulting MST, in the order of the time they are added to the MST.Explanation / Answer
1) Sort all edged in increasing order of their weight
Pick smallest edge and check if it forms a cycle in the minimum spanning tree, if cycle is not formed include otherwise exclude.
So let us sort them in order according to weight
Now let us start from first edge and see if it forms a cycle
Edge Weight B-C 1 A-B 2 C-D 3 B-D 4 A-E 5 E-F 6 D-E 7 A-B 8 C-F 9