New Month End Dhamaka - Flat 55% Off on All Courses

    Question

    Which condition must be satisfied for Kruskal’s

    Algorithm to function correctly?
    A The graph must be directed. Correct Answer Incorrect Answer
    B The graph must be connected. Correct Answer Incorrect Answer
    C The graph must be weighted. Correct Answer Incorrect Answer
    D All edge weights must be distinct. Correct Answer Incorrect Answer
    E The graph must have no cycles. Correct Answer Incorrect Answer

    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.

    Practice Next