New Register here for RBI, SEBI & NABARD strategy workshop! April 9 at 7 PM

    Question

    Which data structure is used in Prim’s Algorithm to

    efficiently find the minimum edge connecting a vertex to the spanning tree?
    A Binary Search Tree Correct Answer Incorrect Answer
    B Adjacency List Correct Answer Incorrect Answer
    C Min-Heap (Priority Queue) Correct Answer Incorrect Answer
    D Adjacency Matrix Correct Answer Incorrect Answer
    E Disjoint Set Correct Answer Incorrect Answer

    Solution

    In Prim’s Algorithm, a Min-Heap (Priority Queue) is used to efficiently find and extract the minimum-weight edge connecting a vertex to the existing spanning tree. The Min-Heap allows quick updates to edge weights and ensures that the minimum-weight edge can be retrieved in O(log⁡V) time, where V is the number of vertices. Steps: • Initialize a Min-Heap with all vertices, starting with an arbitrary vertex having weight 0. • Update the heap when shorter edges are discovered. • Extract the vertex with the minimum edge weight, adding it to the Minimum Spanning Tree (MST). This data structure optimizes the algorithm's overall complexity to O(Elog⁡V), making it suitable for dense graphs. Why Other Options Are Incorrect: 1. Binary Search Tree: Inefficient for handling dynamic updates and retrieval of minimum elements. 2. Adjacency List: Represents graph structure but does not facilitate edge selection. 3. Adjacency Matrix: Useful for graph representation but inefficient for edge extraction in MST. 4. Disjoint Set: Used in Kruskal’s Algorithm to detect cycles, not for edge selection in Prim’s Algorithm. Min-Heaps are integral to Prim’s efficiency in handling dynamic graph traversal during MST construction.

    Practice Next