Back to the 2024 paper

Module 3: Graph and Tree Algorithms

20242m

Which algorithm is used to find a Minimum Spanning Tree?
(i) Dijkstra's algorithm
(ii) Prim's algorithm
(iii) Bellman-Ford algorithm
(iv) Floyd-Warshall algorithm

Worked SolutionAI Assisted

Answer: (ii) Prim's algorithm

Explanation:

  • MST algorithms: Prim's (O(Elog⁡V)O(E \log V) with heap, O(E+Vlog⁡V)O(E+V\log V) with Fibonacci heap) and Kruskal's (O(Elog⁡E)O(E \log E)) both find Minimum Spanning Tree.
  • Dijkstra's, Bellman-Ford, Floyd-Warshall are shortest-path algorithms, not MST.
  • Among given options, (ii) Prim's is the only MST algorithm.

Note: Q81 lists Kruskal's as option (ii) — both Prim's and Kruskal's are correct MST algorithms; the exam chooses whichever appears in options.

Correct choice: (ii)

Similar questions

Official AppAndroid App

PYQDeck for Android

Solve BEU previous-year exam papers anywhere, anytime. Fast search, offline paper viewing, and step-by-step solutions designed specifically for your phone.