This set of Data Structures & Algorithms Multiple Choice Questions & Answers (MCQs) focuses on “Prim’s Algorithm”.
1. Which of the following is true?
a) Prim’s algorithm initialises with a vertex
b) Prim’s algorithm initialises with a edge
c) Prim’s algorithm initialises with a vertex which has smallest edge
d) Prim’s algorithm initialises with a forest
View Answer
Explanation: Steps in Prim’s algorithm: (I) Select any vertex of given graph and add it to MST (II) Add the edge of minimum weight from a vertex not in MST to the vertex in MST; (III) It MST is complete the stop, otherwise go to step (II).
2. Consider the given graph.
What is the weight of the minimum spanning tree using the Prim’s algorithm,starting from vertex a?
a) 23
b) 28
c) 27
d) 11
View Answer
Explanation: In Prim’s algorithm, we select a vertex and add it to the MST. Then we add the minimum edge from the vertex in MST to vertex not in MST. From, figure shown below weight of MST = 27.
3. Worst case is the worst case time complexity of Prim’s algorithm if adjacency matrix is used?
a) O(log V)
b) O(V2)
c) O(E2)
d) O(V log E)
View Answer
Explanation: Use of adjacency matrix provides the simple implementation of the Prim’s algorithm. In Prim’s algorithm, we need to search for the edge with a minimum for that vertex. So, worst case time complexity will be O(V2), where V is the number of vertices.
4. Prim’s algorithm is a ______
a) Divide and conquer algorithm
b) Greedy algorithm
c) Dynamic Programming
d) Approximation algorithm
View Answer
Explanation: Prim’s algorithm uses a greedy algorithm approach to find the MST of the connected weighted graph. In greedy method, we attempt to find an optimal solution in stages.
5. Prim’s algorithm resembles Dijkstra’s algorithm.
a) True
b) False
View Answer
Explanation: In Prim’s algorithm, the MST is constructed starting from a single vertex and adding in new edges to the MST that link the partial tree to a new vertex outside of the MST. And Dijkstra’s algorithm also rely on the similar approach of finding the next closest vertex. So, Prim’s algorithm resembles Dijkstra’s algorithm.
6. Kruskal’s algorithm is best suited for the sparse graphs than the prim’s algorithm.
a) True
b) False
View Answer
Explanation: Prim’s algorithm and Kruskal’s algorithm perform equally in case of the sparse graphs. But Kruskal’s algorithm is simpler and easy to work with. So, it is best suited for sparse graphs.
7. Consider the graph shown below.
Which of the following edges form the MST of the given graph using Prim’a algorithm, starting from vertex 4.
a) (4-3)(5-3)(2-3)(1-2)
b) (4-3)(3-5)(5-1)(1-2)
c) (4-3)(3-5)(5-2)(1-5)
d) (4-3)(3-2)(2-1)(1-5)
View Answer
Explanation: The MST for the given graph using Prim’s algorithm starting from vertex 4 is,
So, the MST contains edges (4-3)(3-2)(2-1)(1-5).
8. Prim’s algorithm is also known as __________
a) Dijkstra–Scholten algorithm
b) Borůvka’s algorithm
c) Floyd–Warshall algorithm
d) DJP Algorithm
View Answer
Explanation: The Prim’s algorithm was developed by Vojtěch Jarník and it was latter discovered by the duo Prim and Dijkstra. Therefore, Prim’s algorithm is also known as DJP Algorithm.
9. 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
View Answer
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).
10. 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
View Answer
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.
Sanfoundry Global Education & Learning Series – Data Structures & Algorithms.
To practice all areas of Data Structures & Algorithms, here is complete set of 1000+ Multiple Choice Questions and Answers.
- Check Computer Science Books
- Practice Data Structure MCQ
- Check Design and Analysis of Algorithms Books
- Practice Computer Science MCQs
- Practice Programming MCQs
