(a) There is a weighted undirected graph in Fig 5. There are six nodes. A, B, C,
ID: 3817282 • Letter: #
Question
(a) There is a weighted undirected graph in Fig 5. There are six nodes. A, B, C, D, E, and F. The value beside 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 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
Kruskal Algorithm:
1. Pick the least edge, and add it to MST, provided both edge doesn't form a loop in MST.
Repeat this process till all vertices are added.
Following this process:
First lets order the edges in ascending order...
(B, C): 1
(A, F): 2
(C, D): 3
(B, D): 4
(A, E): 5
(E, F): 6
(D, E): 7
(A, B): 8
(C, F): 9.
Now, the order in which edges are added to the MST is:
(B, C) -> (A, F) -> (C, D) -> (A, E) -> (D, E).
Prims Algorithm:
1. Pick the least edge, and add it to MST, provided one edge is part of MST, and the other
is not. Repeat this process till all vertices are added.
Following this process:
First lets order the edges in ascending order...
(B, C): 1
(A, F): 2
(C, D): 3
(B, D): 4
(A, E): 5
(E, F): 6
(D, E): 7
(A, B): 8
(C, F): 9.
Now, the order in which edges are added to the MST is:
(B, C) -> (C, D) -> (D, E) -> (A, E) -> (A, F)
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.