Question

Consider the given two statements:
S1: Kruskal’s Algorithm might produce a non-minimal spanning tree.
S2: Kruskal’s Algorithm can be efficiently implemented using the disjoint set data structure.
Choose the correct answer from the options given below:

• A. S1 is true but S2 is false
• B. Both S1 and S2 are false
• C. Both S1 and S2 are true
• D. S2 is true but S1 is false

Hint:

Always remember, Kruskal’s Algorithm guarantees an MST when applied on a connected and undirected graph.

Answer 1

The Correct Option is D

- S1 is false: Kruskal’s Algorithm always produces a minimal spanning tree as it selects edges in increasing order of weights without forming cycles. - S2 is true: Disjoint set data structures are used to efficiently manage the connected components while executing Kruskal’s Algorithm.