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:

Both algorithms give an MST of the same minimum total weight, but they choose edges by different rules (Prim: edge leaving the growing tree; Kruskal: smallest edge not forming a cycle).

Answer 1

The Correct Option is C

Step 1: Understanding the Question:

We must judge the Assertion (A) about the minimum spanning trees (MSTs) produced by Prim's and Kruskal's algorithms and the Reason (R) about how they pick edges.

Step 2: Detailed Explanation:

• Assertion (A): For a connected weighted graph, the total weight of a minimum spanning tree is a fixed value. Both Prim's and Kruskal's algorithms are correct MST algorithms, so both always return a spanning tree of this same minimum total weight. Hence (A) is correct (the question speaks of the same minimum total weight).

• Reason (R): Prim's algorithm grows one tree and, at each step, picks the minimum weight edge that connects the current tree to a new vertex. Kruskal's algorithm instead picks the globally smallest edge that does not form a cycle, joining separate components of a forest. The two do not use the same edge selection rule at each step, so (R) as stated is not correct and cannot be the explanation of (A).

Step 3: Final Answer:
(A) is correct but (R) is not correct. The correct option is (C) (A) is correct but (R) is not correct.