Algorithms
October 4, 2023Programming
October 4, 2023Algorithms
| Question 18 |
Consider the undirected graph below:
Using Prim’s algorithm to construct a minimum spanning tree starting with node A, which one of the following sequences of edges represents a possible order in which the edges would be added to construct the minimum spanning tree?
| (E, G), (C, F), (F, G), (A, D), (A, B), (A, C) | |
| (A, D), (A, B), (A, C), (C, F), (G, E), (F, G) | |
| (A, B), (A, D), (D, F), (F, G), (G, E), (F, C) | |
| (A, D), (A, B), (D, F), (F, C), (F, G), (G, E)
|
Question 18 Explanation:
(A) and (B) produce disconnected components with the given order in options which is never allowed by Prim’s algorithm.
(C) produces connected component every instead a new edge is added but when first vertex is chosen (first vertex is chosen randomly) first edge must be minimum weight edge that is chosen. Therefore, (A, D) must be chosen before (A, B). Therefore (C) is false.
(C) produces connected component every instead a new edge is added but when first vertex is chosen (first vertex is chosen randomly) first edge must be minimum weight edge that is chosen. Therefore, (A, D) must be chosen before (A, B). Therefore (C) is false.
Correct Answer: D
Question 18 Explanation:
(A) and (B) produce disconnected components with the given order in options which is never allowed by Prim’s algorithm.
(C) produces connected component every instead a new edge is added but when first vertex is chosen (first vertex is chosen randomly) first edge must be minimum weight edge that is chosen. Therefore, (A, D) must be chosen before (A, B). Therefore (C) is false.
(C) produces connected component every instead a new edge is added but when first vertex is chosen (first vertex is chosen randomly) first edge must be minimum weight edge that is chosen. Therefore, (A, D) must be chosen before (A, B). Therefore (C) is false.