Teaching UGC NET Mock Test Series 2025 (Paper 1 & 2) Algorithms Graphs/Spanning Tree and Shortest Paths Spanning Tree
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?
1
(a, b), (b, h), (g, h), (f, g), (c, f), (c, i), (c, d), (d, e)
2
(a, b), (b, h), (g, h), (g, i), (c, i), (c, f), (c, d), (d, e)
3
(a, b), (b, c), (c, i), (c, f), (f, g), (g, h), (c, d), (d, e)
4
(a, b), (g, h), (g, f), (c, f), (c, i), (f, e), (b, c), (d, e)