McqMate

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 |

Answer» A. d-ary heap | |

Explanation: 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). |

2.2k

0

Do you find this helpful?

25

View all MCQs in

Design and Analysis of AlgorithmsNo comments yet

- Kruskal’s algorithm is best suited for the dense graphs than the prim’s algorithm.
- Kruskal’s algorithm is best suited for the sparse graphs than the prim’s algorithm.
- Which of the following algorithm can be used to solve the Hamiltonian path problem efficiently?
- Suppose you have coins of denominations 1,3 and 4. You use a greedy algorithm, in which you choose the largest denomination coin which is not greater than the remaining sum. For which of the following sums, will the algorithm produce an optimal answer?
- Fractional knapsack problem is solved most efficiently by which of the following algorithm?
- Given G is a bipartite graph and the bipartitions of this graphs are U and V respectively. What is the relation between them?
- In graphs, in which all vertices have an odd degree, the number of Hamiltonian cycles through any fixed edge is always even.
- Which algorithm is the most efficient numerical algorithm to obtain lcm?
- The running time of Bellmann Ford algorithm is lower than that of Dijkstra’s Algorithm.
- Dijikstra’s Algorithm is more efficient than Bellmann Ford Algorithm.