- Prepare
- All Platforms
- Programming
- Aptitude
- Syllabus
- Interview Preparation
- Interview Exp.
- Off Campus
- Prime Video
- Prime Mock

- PrepInsta Prime
- OffCampus
- Internship
- Placement Stats
- Prime Video
- Prime Mock

^{0}Notifications Mark All Read

No New notification

- Login
- Get Prime

# 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