Question
Which data structure is used in Primās Algorithm to
efficiently find the minimum edge connecting a vertex to the spanning tree?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.
What is the primary goal of the Maritime Development Fund (MDF)?
Which award did Rishab Shetty win at the 70th National Film Awards for the year 2022?
_____________ was India’s top trading partner in the calendar year 2021 with a trade of $112.3 billion.
The Supersonic Missile-Assisted Release of Torpedo (SMART) system enhances which aspect of naval warfare?
In which town is India's largest reclining statue of Lord Buddha currently under construction, with dimensions of 100 feet in length and 30 feet in height?
Which Sikkim district is home to Indiaās first digital nomad village, Yakten?
What is the rank of Indian passport as per Henley Passport Index 2023?
What is the main objective of the MoU signed between DPIIT and NCAER?
Which bank have been adjudged 'Most Innovative Best Practice' for financial inclusion at the CII Digital Transformation Award 2021?
Which country will host the BRICS Esports Championship 2025?