Algorithms
October 4, 2023Programming
October 4, 2023Algorithms
| Question 4 |
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 4 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 4 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.
Subscribe
Login
0 Comments