Mr. Dubey • 100.69K Points
Coach

Q. Prim’s algorithm can be efficiently implemented using for graphs with greater density.

(A) d-ary heap
(B) linear search
(C) fibonacci heap
(D) binary search

Correct Answer - Option(A)
Views: 442
Filed under category Design and Analysis of Algorithms

Explanation by: Mr. Dubey

in prim’s algorithm, we add the minimum weight edge for the chosen vertex which requires searching on the array of weights. this searching can be efficiently implemented using binary heap for dense graphs. and for graphs with greater density, prim’s algorithm can be made to run in linear time using d-ary heap(generalization of binary heap).

You must be Logged in to update hint/solution