Prim's Algorithm Multiple choice Questions and Answers (MCQs)
Click on any option to know the CORRECT ANSWERS
Which of the following is true?
Prim's algorithm initialises with a vertex
Prim's algorithm initialises with a edge
Prim's algorithm initialises with a vertex which has smallest edge
Prim's algorithm initialises with a forest
Question 1 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).
Consider the given graph.
What is the weight of the minimum spanning tree using the Prim's algorithm, starting from vertex a?
Worst case is the worst case time complexity of Prim's algorithm if adjacency matrix is used?
O(V log E)
Question 3 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.
Prim's algorithm is a .....
Divide and conquer algorithm
Question 4 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.
Prim's algorithm resembles Dijkstra's algorithm.
Question 5 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.
There are 5 questions to complete.