Question

Given below are two statements :
one is labelled as
Assertion (A) and the other is labelled as
Reason (R).
Assertion (A) :
Prim’s and Kruskal’s algorithms always produce the same minimum total weight spanning tree for a given connected, weighted graph.
Reason (R) :
Both algorithms use same greedy properties of choosing the minimum weight edge at each step.
In the light of the above statements, choose the most appropriate answer from the options given below :

• A. Both (A) and (R) are correct and (R) is the correct explanation of (A)
• B. Both (A) and (R) are correct but (R) is not the correct explanation of (A)
• C. (A) is correct but (R) is not correct
• D. (A) is not correct but (R) is correct

Hint:

Remember: Unique edge weights $\implies$ Unique MST. Duplicate edge weights $\implies$ Multiple possible MSTs!

Answer 1

The Correct Option is D

Concept:
• A Minimum Spanning Tree (MST) is a subset of edges that connects all vertices without cycles and with the minimum possible total edge weight.
• Prim's algorithm builds the tree one vertex at a time.
• Kruskal's algorithm builds the tree by processing edges in increasing order of weight.

Step 1: Evaluate Assertion (A)
While Prim's and Kruskal's will always find a spanning tree with the same minimum total weight, they do not necessarily produce the same set of edges (the same tree). If a graph has multiple edges with the same weight, there can be multiple distinct MSTs. Prim's might choose one edge while Kruskal's chooses a different one with an identical weight. Thus, (A) is false.

Step 2: Evaluate Reason (R)
Both algorithms are indeed greedy. Prim's greedily picks the minimum weight edge connected to the current growing tree. Kruskal's greedily picks the absolute minimum weight edge from the entire remaining set (that doesn't form a cycle). This shared greedy philosophy is correct. Thus, (R) is true.