Which condition must be satisfied for Kruskal’s

Solution

Kruskal’s Algorithm constructs a Minimum Spanning Tree (MST) by selecting the smallest edges while ensuring no cycles are formed. For the algorithm to function correctly, the graph must be connected, meaning there exists a path between any two vertices. In a disconnected graph, Kruskal’s Algorithm would result in a Minimum Spanning Forest, not a single tree. Connectivity ensures that all vertices are included in a unified MST. Steps: • Sort edges by weight. • Use a Disjoint Set to detect and prevent cycles. • Add edges until all vertices are connected. Why Other Options Are Incorrect: 1. Directed Graph: Kruskal works on undirected graphs; additional considerations are needed for directed graphs. 2. Weighted Graph: While weights are essential, connectivity is a stricter requirement. 3. Distinct Weights: Not required; ties can be resolved arbitrarily. 4. No Cycles: The algorithm actively avoids cycles but does not require the graph to be cycle-free initially. Kruskal’s reliance on graph connectivity is a cornerstone of its application in MST problems.