Question

Which of the following is false about Prim’s algorithm?

(a) It is a greedy algorithm

(b) It constructs MST by selecting edges in increasing order of their weights

(c) It never accepts cycles in the MST

(d) It can be implemented using the Fibonacci heap

The question was posed to me in an interview for internship.

I want to ask this question from Minimum Spanning Tree in chapter Minimum Spanning Tree of Data Structures & Algorithms II

Answer 1

Correct choice is (b) It constructs MST by selecting edges in increasing order of their weights

For explanation: Prim’s algorithm can be implemented using Fibonacci heap and it never accepts cycles. And Prim’s algorithm follows greedy approach. Prim’s algorithms span from one vertex to another.