Minimum Spanning Tree (a) There is a weighted undirected graph in Fig. 5. There

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

Related Questions

Navigate

• Browse (All)
• Browse M
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.