Scribd
Upload
5 views2 pages

Data Structures Used by Prims Algorithm

The document outlines the data structures used in Prim's Algorithm for finding the minimum spanning tree (MST). Key structures include a graph representation (adjacency list or matrix), a visited set/array to track included vertices, and an optional parent array for reconstructing the MST. A priority queue (min-heap) is also essential for efficiently selecting the next minimum-weight edge during the algorithm's execution.

Uploaded by

calebbrandon999
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
5 views2 pages

Data Structures Used by Prims Algorithm

The document outlines the data structures used in Prim's Algorithm for finding the minimum spanning tree (MST). Key structures include a graph representation (adjacency list or matrix), a visited set/array to track included vertices, and an optional parent array for reconstructing the MST. A priority queue (min-heap) is also essential for efficiently selecting the next minimum-weight edge during the algorithm's execution.

Uploaded by

calebbrandon999
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd

Prims Algorithm ……Data structures used

 Graph Representation:It is usually implemented as a min-heap, is the most crucial data


structure for an efficient implementation. It stores the edges (or vertices, ordered by the
connecting edge's weight) that connect the growing minimum spanning tree (MST) to the
remaining vertices. This allows for the efficient selection of the minimum-weight edge at each
step of the algorithm. The graph itself can be stored using an adjacency list or an
adjacency matrix. Adjacency lists are generally more space-efficient for sparse graphs.

 Visited Set/Array: A boolean array or a set is used to keep track of the vertices that
have already been included in the MST, preventing cycles and redundant processing.

 Parent Array (Optional): A parent array or a similar structure can be used to store the
edges that form the MST, allowing the reconstruction of the final tree once the algorithm
completes

 Graph Representation (Adjacency List or Matrix):

o How it's used: This structure stores the graph itself, including the vertices
and the weighted edges between them.

o It uses a two-dimensional matrix, in which the rows represent source vertices and
columns represent destination vertices. Data on edges and vertices must be
stored externally

o The algorithm needs quick access to all edges connected to a specific


vertex as it expands the Minimum Spanning Tree (MST).

o Variations: An adjacency list is typically used for sparse graphs (fewer


edges relative to vertices) for memory efficiency and better performance
with a priority queue. An adjacency matrix is better suited for dense
graphs, offering quick O(1) access to any edge's weight.

 Priority Queue (Min-Heap):

o How it's used: The priority queue, usually implemented as a min-heap, is


crucial for efficiently selecting the next minimum-weight edge that
connects a vertex in the growing MST to a vertex outside it. Edges (or
vertices with their connecting weights) are stored in the queue, ordered by
their weight. The minimum-weight item can be extracted in logarithmic
time, which is key to the algorithm's performance.

 Set or Boolean Array (Visited Set):


Prims Algorithm ……Data structures used

o How it's used: A set or a simple boolean array is used to keep track of all
the vertices that have already been included in the MST.

o Purpose: This prevents the algorithm from adding a vertex to the MST
twice and ensures that no cycles are formed, a fundamental requirement
of a spanning tree.

 Parent Array (Optional):

o How it's used: An optional array can store the "parent" of each vertex in
the final MST. This structure allows the actual edges of the MST to be
reconstructed after the algorithm completes.
References

[Link]

[Link]

You might also like