Q36.Marks: +2.0UGC NET Paper 2: Computer Science 2nd January 2026 Shift 1
Given below are two statements: one is labelled as Assertion A and the other is labelled as Reason R Assertion A: Kruskal's algorithm and Prim's algorithm always produce minimum spanning tree (MST). Reason R: Every connected graph has a unique MST.
In the light of the above statements, choose the most appropriate answer from the options given below
1.Both A and R are correct and R is the correct explanation of A
2.Both A and R are correct but R is NOT the correct explanation of A
3.A is correct but R is not correct✓ Correct
4.A is not correct but R is correct
Solution
The correct answer is A is correct but R is not correct.
Key Points
Kruskal's algorithm and Prim's algorithm are two well-known algorithms used to find a Minimum Spanning Tree (MST) of a connected, weighted graph.
Both algorithms are designed to always produce a valid MST.
However, Reason R is incorrect because not every connected graph has a unique MST. A graph can have multiple MSTs if there are edges with the same weights.
For instance, in a graph where multiple edges have the same weight, different algorithms or tie-breaking strategies can lead to different valid MSTs.
Thus, the correct conclusion is that A is correct but R is not correct.
Additional Information
Kruskal's Algorithm:
It is a greedy algorithm that builds the MST by selecting the smallest edge at every step, ensuring no cycles are formed.
It works well with sparse graphs where the number of edges is relatively low compared to the number of vertices.
Prim's Algorithm:
It is another greedy algorithm that builds the MST by starting from an arbitrary vertex and expanding the tree by adding the smallest edge connected to the tree.
It is particularly efficient for dense graphs where the number of edges is high.
Important Points:
A Minimum Spanning Tree is a subset of edges that connects all vertices of the graph with the minimum possible total edge weight.
In cases where multiple edges have the same weight, there can be more than one MST for the same graph.
Both Kruskal's and Prim's algorithms guarantee finding an MST, but they may produce different MSTs in graphs with multiple valid solutions.
