Prim's Minimum Spanning Tree Algorithm

Prim's Algorithm by Lalitha Natraj
ðŸ”—
Prim's Algorithm by William Fiset
ðŸ”—

Prim’s algorithm is a graph-based algorithm used to construct a Minimum Spanning Tree (MST) for a given weighted, undirected graph. It builds the MST by greedily selecting the lowest-weight 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 minimum-weight 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 long-term 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:

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.

Step-by-step process of Prim’s algorithm:

1. 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 min-heap) to store unused edges connected to the current MST.
2. Growing the MST:

• While the MST set does not contain all the vertices:
• Select and remove the minimum-weight 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.
3. 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 minimum-weight 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
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

# 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

# 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 min-heap) 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 to `V * V-1` if each node in the graph has a link to every other node in the graph, the heap operation takes `O(log V^2)` which is `2*O(log V)` which in turn can be approximated to `O(log V)`.
• Similarly, extracting the minimum-weight 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)`.