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 invariably constructs a minimal spanning tree by prioritizing edges of ascending weight and preventing cycle creation. - S2 is true: Disjoint set data structures facilitate efficient management of connected components throughout Kruskal's Algorithm execution.