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:

2. Find the smallest connecting road: From the tree, pick the shortest road connecting to a point outside the tree.
4. 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:

2. Find the smallest connecting road: From the tree, pick the shortest road connecting to a point outside the tree.
4. 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

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).

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).

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).

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:
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.

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