Prim’s algorithm is a graphbased algorithm used to construct a Minimum Spanning Tree (MST) for a given weighted, undirected graph. It builds the MST by greedily selecting the lowestweight edge that connects a vertex in the growing MST to a vertex outside it. Prim’s algorithm maintains a priority queue to efficiently select the next minimumweight edge, ensuring that at each step, it chooses the cheapest way to expand the MST without creating cycles. This process continues until all vertices are included in the MST.
Prim’s algorithm is a greedy algorithm, meaning it always chooses the cheapest edge at each step, without considering the longterm consequences of its choices. Despite its simplicity, Prim’s algorithm is proven to be efficient and effective in finding the MST of a weighted, connected graph.
What is a Minimum Spanning Tree?
A Minimum Spanning Tree (MST) is a subset of the edges of a connected, weighted graph that connects all the vertices together with the minimum possible total edge weight. In other words, it is the cheapest or minimum cost subgraph in a given graph that connects all the nodes in the graph.
For example, for the undirected weighted graph shown below:
Below is how the minimum spanning tree looks like:
Refer to this article to learn more about Minimum Spanning Trees.
Detailed Steps of Prim’s MST Algorithm
Prim’s algorithm builds the MST incrementally, starting with a single vertex and expanding the tree by adding the cheapest possible edge from the tree to a vertex not yet in the tree. It maintains a growing set of vertices that are part of the MST and continuously adds the smallest weight edge that connects a vertex in the MST to a vertex outside the MST.
Stepbystep process of Prim’s algorithm:

Initialization:
 Select an arbitrary vertex to start the MST. This vertex is the initial member of the MST set.
 Initialize a set to keep track of vertices included in the MST.
 Create an array to store the minimum cost edge that connects each vertex to the growing MST. Initialize the starting vertex’s cost to zero and others to infinity.
 Use a priority queue (or a minheap) to store unused edges connected to the current MST.

Growing the MST:
 While the MST set does not contain all the vertices:
 Select and remove the minimumweight edge from the priority queue.
 If the edge connects to a vertex already in the MST, discard it and continue.
 Otherwise, add this edge to the MST and the new vertex to the MST set.
 For each adjacent vertex of the extracted vertex, if the vertex is not yet in the MST, add the edge to priority queue.
 While the MST set does not contain all the vertices:

Termination:
 The process continues until all vertices are included in the MST set.
The use of a priority queue allows for efficient selection of the minimumweight edge at each step. If priority queue is not used, we would need to sort all edges every time a new edge is added.
Implementation
import heapq
# Function to find the minimum spanning tree
# Using Prim's Minimum Spanning Tree Algorithm
def prims_mst(graph, start_node):
# Initialize a set to keep track of nodes
# Which are already added to the MST
visited = set()
# Initialize a priority queue to store the edges
pq = []
# Initialize the total weight of the MST
total_weight = 0
# Initialize a list to store the edges in the MST
mst_edges = []
# Add the starting node to the visited set
visited.add(start_node)
# Add all the edges from the starting node to the priority queue
for neighbor, weight in graph[start_node]:
heapq.heappush(pq, (weight, start_node, neighbor))
# While the priority queue is not empty
while pq:
# Pop the edge with the minimum weight from the priority queue
weight, u, v = heapq.heappop(pq)
# If the destination node has not been visited yet
if v not in visited:
# Add the edge to the MST
mst_edges.append((u, v, weight))
# Add the weight of the edge to the total weight
total_weight += weight
# Add the destination node to the visited set
visited.add(v)
# Add all the edges from the new node to the priority queue
for neighbor, neighbor_weight in graph[v]:
if neighbor not in visited:
heapq.heappush(pq, (neighbor_weight, v, neighbor))
# Return the total weight and the edges in the MST
return mst_edges, total_weight
if __name__ == "__main__":
# Graph represented as adjacency list
graph = {
"A": [("B", 8), ("D", 2), ("E", 4)],
"B": [("A", 8), ("C", 7), ("F", 4)],
"C": [("B", 7), ("D", 9), ("F", 6)],
"D": [("A", 2), ("C", 9), ("E", 5)],
"E": [("A", 4), ("D", 5), ("F", 3)],
"F": [("B", 4), ("C", 6), ("E", 3)],
}
mst, total_weight = prims_mst(graph, "A")
print("Minimum Spanning Tree edges:")
for edge in mst:
print(f"({edge[0]}  {edge[1]}) with weight {edge[2]}")
print(f"Total weight of MST: {total_weight}")
Time and Space Complexity
Time Complexity:
The time complexity of Prim’s algorithm depends on how dense the graph is and the data structure used to store and retrieve available edges. The most common implementation uses a priority queue (e.g., a minheap) to efficiently select the next vertex to add to the MST. With a priority queue, the time complexity of Prim’s algorithm is O(E log V)
, where E
is the number of edges in the graph and V
is the number of vertices in the graph.
This is because the algorithm needs to:
 Inserting each vertex into the priority queue takes
O(log V)
per edge. Note: Although the heap/priority queue size can grow toV * V1
if each node in the graph has a link to every other node in the graph, the heap operation takesO(log V^2)
which is2*O(log V)
which in turn can be approximated toO(log V)
.  Similarly, extracting the minimumweight vertex from the priority queue takes
O(log V)
per extraction
The algorithm performs these operations for a maximum of E
times, resulting in the overall time complexity of O(E log V)
.
Space Complexity:
The space complexity of Prim’s algorithm is O(E + V)
, as the algorithm needs to store the following data structures:
 A priority queue to keep track of the vertices and their weights which can take a maximum of
O(V)
space  A set or array to keep track of the vertices that have already been added to the MST which takes
O(V)
space
Therefore, the overall space complexity of Prim’s algorithm is O(E + V)
.