What Is Prim’s Algorithm?
Prim’s Algorithm is a greedy algorithm used to find a Minimum Spanning Tree (MST) from a weighted, connected, undirected graph.
Table Of Content
- What Is Prim’s Algorithm?
- How Prim’s Algorithm Works (Step-by-Step)
- Pseudocode for Prim’s Algorithm
- Example Implementation (Python)
- Let’s take a sample weighted graph
- Total MST Cost = 2 + 4 + 5 = 11
- Prim’s Algorithm vs Kruskal’s Algorithm
- Real World Applications of Prim’s Algorithm
- When / Why Use Prim’s Algorithm
- Conclusion
- Related Reads
Yep — that’s the one-line exam-ready answer. But let’s make it human.
Think of Prims like building a road network between multiple cities using the minimum cost possible, without creating loops.
You start from one city (any city), pick the cheapest connection, then from the visited cities pick the next cheapest edge… and you repeat.
How Prim’s Algorithm Works (Step-by-Step)
-
Pick any vertex as a starting point. Mark it “visited” / “in MST”.
-
Look at all edges from visited vertices that go to unvisited vertices.
-
Choose the edge with the smallest weight among them. Add that edge + the new vertex to MST (mark visited).
-
Update the list of “candidate edges”: now include edges from this newly added vertex (that lead to unvisited vertices).
-
Repeat steps 2–4 until all vertices are visited / included.
Because we always pick the cheapest available edge that expands the tree — we ensure the total cost remains minimal.
This greedy, “grow-step-by-step” nature makes Prim’s algorithm efficient and intuitive when you visualize graphs.
Pseudocode for Prim’s Algorithm
function Prim(graph):
MST = empty set of edges
start = any vertex in graph
visited = { start }
candidateEdges = all edges from start
while visited does not include all vertices:
edge = the edge from candidateEdges with minimum weight
(u, v, w) = edge // u: visited side, v: unvisited side
add edge to MST
add v to visited
remove that edge from candidateEdges
add to candidateEdges all edges from v that lead to unvisited vertices
return MST
(Note: Implementation details — like how you store edges, pick minimum efficiently — may vary depending on graph representation.)
This pseudocode aligns with common textbook/explanation versions of Prim’s algorithm.
Example Implementation (Python)
import heapq
def prim(graph, start):
visited = set([start])
edges = [
(weight, start, to_node)
for to_node, weight in graph[start]
]
heapq.heapify(edges)
mst = []
while edges:
weight, frm, to = heapq.heappop(edges)
if to not in visited:
visited.add(to)
mst.append((frm, to, weight))
for next_node, next_weight in graph[to]:
if next_node not in visited:
heapq.heappush(edges, (next_weight, to, next_node))
return mst
If you define the graph as adjacency lists (with nodes mapped to lists of (neighbor, weight)), this gives the MST edges as mst. This is a common efficient way to implement Prim’s algorithm using a priority queue (heap) — which improves performance, especially for sparse graphs.
Let’s take a sample weighted graph:
(2)
A ------- B
| \ |
4 3 5
| \ |
C ------- D
(6)
Step-by-step using Prim’s:
| Step | Chosen Edge | Weight | MST Nodes |
|---|---|---|---|
| 1 | Start at A | — | A |
| 2 | A → B | 2 | A, B |
| 3 | A → C | 4 | A, B, C |
| 4 | B → D | 5 | A, B, C, D |
Total MST Cost = 2 + 4 + 5 = 11
No cycles.
All nodes connected.
Prim’s Algorithm vs Kruskal’s Algorithm
| Feature | Prim’s | Kruskal’s |
|---|---|---|
| Approach | Grows from a starting node | Sorts & connects edges globally |
| Works well with | Dense graphs | Sparse graphs |
| Data structure support | Priority Queue (Binary Heap) | Disjoint Set (Union-Find) |
| Initial choice | Random starting vertex required | No starting vertex |
Real World Applications of Prim’s Algorithm
-
🛰 Network Routing
-
🛣 Road and Railway Planning
-
🌐 Internet backbone cable design
-
📡 Telecommunication tower placement
-
🤖 AI and Robotics path optimization
-
🕸 Graph-based clustering algorithms
When / Why Use Prim’s Algorithm
Prim’s algorithm (or its variants) appears in many practical scenarios:
-
Designing networks (like fiber-optic cables, electricity grids, transportation, roads) — whenever you need to connect many points with minimal “cost”.
-
In computer networks / graph-based optimizations — for efficient routing or clustering.
-
In image segmentation, bioinformatics, or spanning-tree protocols — anywhere MST logic helps reduce redundancy while maintaining connectivity.
Basically, when the problem can be modeled as “connect all points, minimize total connection cost, avoid loops” — Prim’s algorithm is your friend.
Conclusion
I hope this article helped you understand Prim’s algorithm in a clear, beginner-friendly way — just like I wished someone had explained to me when I first saw MSTs.
Whether you’re preparing for coding interviews, studying graph theory, or building real-world networks — this greedy but powerful algorithm gives you a dependable tool
Want Learn More?, Kaashiv Infotech Offers Cloud Computing Course, Cyber Security Course, Networking Course & More, Visit Our Website www.kaashivinfotech.com.
Related Reads:
