Prim’s Algorithm
Prim’s Algorithm Python Implementation:
Prim’s algorithm, a fundamental concept in graph theory, is a vital tool for solving complex network problems. Whether you’re optimizing network connections, designing transportation systems, or enhancing resource allocation, understanding Prim’s algorithm is crucial.
In this tutorial, we’ll simplify its logic and Python implementation, equipping you to efficiently apply it to real-world challenges. Let’s dive in! write this type of introduction for prim’s algorithm
What is Prim’s Algorithm?
Prim’s algorithm is a greedy algorithm used to find the minimum spanning tree (MST) of a connected, undirected graph with weighted edges. A minimum spanning tree of a graph is a subgraph that includes all the vertices of the original graph and connects them in such a way that the total sum of the edge weights is minimized.
Here’s how Prim’s algorithm works:
- Start with any point: Begin with one point as your tree.
- Find the smallest connecting road: From the tree, pick the shortest road connecting to a point outside the tree.
- Add the road and the new point: Put this road in your tree, and add the new point.
- Repeat until all points are connected: Keep finding the shortest roads and adding points until everything is connected.
A minimum spanning tree of a graph is a subgraph that includes all the vertices of the original graph and connects them in such a way that the total sum of the edge weights is minimized.
Here’s how Prim’s algorithm works:
- Start with any point: Begin with one point as your tree.
- Find the smallest connecting road: From the tree, pick the shortest road connecting to a point outside the tree.
- Add the road and the new point: Put this road in your tree, and add the new point.
- Repeat until all points are connected: Keep finding the shortest roads and adding points until everything is connected.
Prim’s Algorithm Pseudocode:
Prim(Graph G):
Initialize an empty set MST (minimum spanning tree)
Initialize a priority queue Q with all vertices of G and their corresponding key values (initially set to infinity)
Choose an arbitrary vertex s as the starting point
Update the key value of vertex s to 0 in the priority queue
while Q is not empty:
u = ExtractMin(Q) // Get the vertex with the minimum key value from Q
Add u to MST
for each vertex v adjacent to u:
if v is in Q and the weight of edge (u, v) is less than v's key value:
Update v's key value in Q to the weight of edge (u, v)
Set u as the parent of v in MST
return MST
Working of Prim’s Algorithm:
Let’s go through the working of Prims algorithm with a example.
Consider the following graph:
Step 1 – Initialization:
Start with node A and initialize the priority queue with edges: AB(2), AC(1).
Current Tree:
Step 2 – Select Minimum Weight Edge:
Add edge AB(2) to the tree. Tree: A, B
Current Tree:
Step 3 – Update the Tree and Priority Queue:
Add node B to the tree. Update the priority queue with edges: AC(1), BD(3).
Current Tree:
Step 4 – Select Minimum Weight Edge:
Add edge AC(1) to the tree. Tree: A, B, C
Current Tree:
Step 5 – Update the Tree and Priority Queue:
Add node C to the tree. Update the priority queue with edges: CD(4), BE(3).
Current Tree:
Step 6 – Select Minimum Weight Edge:
Add edge CD(4) to the tree. Tree: A, B, C, D
Current Tree:
Step 7 – Update the Tree and Priority Queue:
Add node D to the tree. Update the priority queue with edge: DE(1).
Current Tree:
Implementation of Prims Algorithm in Python:
Python implementation of Prims algorithm for the given example graph:
from heapq import heappush, heappop
def prim(graph):
min_spanning_tree = []
visited = set()
start_vertex = list(graph.keys())[0]
priority_queue = [(weight, start_vertex, neighbor) for neighbor, weight in graph[start_vertex]]
heappush(priority_queue, (0, None, start_vertex))
while priority_queue:
weight, parent, current_vertex = heappop(priority_queue)
if current_vertex not in visited:
visited.add(current_vertex)
if parent is not None:
min_spanning_tree.append((parent, current_vertex, weight))
for neighbor, edge_weight in graph[current_vertex]:
if neighbor not in visited:
heappush(priority_queue, (edge_weight, current_vertex, neighbor))
return min_spanning_tree
# Example graph represented as an adjacency list
graph = {
'A': [('B', 2), ('C', 1)],
'B': [('A', 2), ('D', 3), ('E', 1)],
'C': [('A', 1), ('D', 4)],
'D': [('B', 3), ('C', 4), ('E', 1)],
'E': [('B', 1), ('D', 1)]
}
minimum_spanning_tree = prim(graph)
print("Minimum Spanning Tree:")
print(minimum_spanning_tree)
Output:
Minimum Spanning Tree:
[('A', 'C', 1), ('C', 'D', 4), ('D', 'E', 1), ('A', 'B', 2)]
In this output, each tuple represents an edge in the minimum spanning tree along with its weight. The minimum spanning tree for the given graph includes the edges (‘A’, ‘C’, 1), (‘C’, ‘D’, 4), (‘D’, ‘E’, 1), and (‘A’, ‘B’, 2).
Prims algorithm time and space complexity:
The time complexity of Prims algorithm is O(E logV) or O(V logV), where E is the number of edges, and V is the number of vertices.
The space complexity is O(V) for an array to know if a node is in MST or not, and O(E) for an array to maintain Min-Heap.
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
Get over 200+ course One Subscription
Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others
Login/Signup to comment