Published: 16 Dec 2025 | Reading Time: 8 min read
This comprehensive guide to Prim's Algorithm provides:
Every major network you use today, including Wi-Fi, electricity grids, and transportation routes, was made possible by an effective solution to a cost-minimization issue. Prim's Algorithm is one of the core ideas that makes this possible.
If you're learning data structures, preparing for interviews, or working with graphs in real systems, understanding Prim's Algorithm is not optional. It directly connects theory (graphs, greedy strategy) with practical optimization problems where cost, distance, or resources must be minimized.
Prim's Algorithm is widely used in competitive programming, examinations, interviews, and actual network design. It also scales well with priority queues. Gaining proficiency in it entails studying how optimum systems are constructed rather than merely remembering code.
When designing networks, whether for computers, power systems, roads, or communication, finding the most efficient way to connect everything is essential. This is where the concept of Minimum Spanning Trees comes in.
A spanning tree is a special kind of subgraph formed from a connected, undirected graph.
In simple terms, a spanning tree connects all points in a network using the minimum number of connections needed, without forming any loops.
A spanning tree containing an additional condition is called a minimal spanning tree. Among all possible spanning trees for a given graph, the MST is the one with the smallest total edge weight. The "weight" here usually represents cost, distance, time, or any measure you want to minimize.
In other words, an MST connects all the vertices together with the least possible total cost.
Example: Imagine cities connected by roads, where each road has a cost to build. A minimum spanning tree would connect all cities together with the least total cost, ensuring there are no unnecessary roads.
Minimum spanning trees are extremely important in real-world optimization problems, such as:
Prim's Algorithm, one of the most important tools for finding minimum spanning trees, has a fascinating history that spans multiple mathematicians and decades.
The original concept was first described by Vojtěch Jarník, a Czech mathematician. Jarník developed a method for efficiently connecting points in a graph with the least total edge weight, laying the early foundations for what we now recognize as Prim's Algorithm.
Almost three decades later, the idea was rediscovered independently by Robert C. Prim, an American mathematician working at Bell Labs. Prim refined the method into a more practical form, suitable for use in real-world applications such as telecommunications network design.
In 1959, the famous computer scientist Edsger W. Dijkstra built upon Prim's work. Dijkstra's improvements and his broader contributions to graph algorithms helped popularize the method even further in the growing field of computer science.
Because of these multiple contributions, the algorithm is known by several names, including:
Prim's Algorithm worked at Bell Labs, paired with Dijkstra's influential optimization strategies, ensured that the algorithm became a standard approach for computing minimum spanning trees in both academic study and modern practical applications.
Prim's algorithm is among the greedy algorithms that are employed to obtain a minimum spanning tree (MST) from a connected, undirected graph. A minimum spanning tree is the set of edges with the minimum total weight, which connects all the vertices of the graph, and does not contain any cycles.
The procedure of the algorithm is to initially take any vertex and then expand the MST by one edge each time. It goes on adding the least edge, which links a vertex in the MST with a vertex outside the MST. The process is repeated until all vertices become part of the MST.
Prim's Algorithm can be implemented in several ways depending on the graph's size and density, as well as the programming language used. Below, you'll find a clear algorithm and pseudocode, explanations of key implementation choices, and sample code in Python, C++, and Java.
Prim's Algorithm starts from a single node and grows the MST one edge at a time.
Important: Cycles are automatically avoided because we only add edges leading to new nodes.
The following pseudocode outlines the general steps of Prim's Algorithm in a language-agnostic way:
PRIM(G = (V, E), w):
for each vertex v in V:
key[v] ← ∞
parent[v] ← NIL
inMST[v] ← false
choose any start vertex s
key[s] ← 0
while there exists a vertex u not in MST:
u ← vertex with minimum key[u] such that inMST[u] = false
inMST[u] ← true
for each vertex v adjacent to u:
if inMST[v] = false and w(u, v) < key[v]:
key[v] ← w(u, v)
parent[v] ← u
return parent
Alternatively, here's a more formal pseudocode variant:
T ← ∅
U ← {starting_vertex}
while U ≠ V do
let (u, v) be the lowest-cost edge
such that u ∈ U and v ∈ (V − U)
T ← T ∪ {(u, v)}
U ← U ∪ {v}
return T
Adjacency Matrix:
Adjacency List:
Tip: For dense graphs, an adjacency matrix with O(V²) complexity is acceptable. For large or sparse graphs, use an adjacency list and a priority queue for optimal O(E log V) performance.
One of the best ways to understand Prim's Algorithm is to follow the example of a simple, weighted, undirected graph, which is done here, step by step, the algorithm grows the Minimum Spanning Tree (MST), and how the auxiliary data structures change at each step.
Consider the graph:
A
/ \
1 3
B----C
\ /
2 4
D
Vertices: {A, B, C, D}
Edges:
We will use an adjacency matrix representation along with a simple array to indicate which nodes are part of the MST.
The MST is complete (it contains V-1 = 3 edges).
Final MST edges:
Total weight: 1 + 2 + 3 = 6
We map vertices to indices for implementation:
| Vertex | Index |
|---|---|
| A | 0 |
| B | 1 |
| C | 2 |
| D | 3 |
#include <stdio.h>
#include <limits.h>
#define V 4
int minKey(int key[], int mstSet[]) {
int min = INT_MAX, minIndex;
for (int v = 0; v < V; v++)
if (!mstSet[v] && key[v] < min)
min = key[v], minIndex = v;
return minIndex;
}
void primMST(int graph[V][V]) {
int parent[V], key[V], mstSet[V];
for (int i = 0; i < V; i++)
key[i] = INT_MAX, mstSet[i] = 0;
key[0] = 0;
parent[0] = -1;
for (int count = 0; count < V - 1; count++) {
int u = minKey(key, mstSet);
mstSet[u] = 1;
for (int v = 0; v < V; v++)
if (graph[u][v] && !mstSet[v] && graph[u][v] < key[v]) {
parent[v] = u;
key[v] = graph[u][v];
}
}
printf("Edge Weight\n");
for (int i = 1; i < V; i++)
printf("%d - %d %d\n", parent[i], i, graph[i][parent[i]]);
}
int main() {
int graph[V][V] = {
{0, 1, 3, 0},
{1, 0, 5, 2},
{3, 5, 0, 4},
{0, 2, 4, 0}
};
primMST(graph);
return 0;
}
#include <iostream>
#include <climits>
using namespace std;
#define V 4
int minKey(int key[], bool mstSet[]) {
int min = INT_MAX, minIndex;
for (int v = 0; v < V; v++)
if (!mstSet[v] && key[v] < min)
min = key[v], minIndex = v;
return minIndex;
}
void primMST(int graph[V][V]) {
int parent[V], key[V];
bool mstSet[V];
for (int i = 0; i < V; i++)
key[i] = INT_MAX, mstSet[i] = false;
key[0] = 0;
parent[0] = -1;
for (int count = 0; count < V - 1; count++) {
int u = minKey(key, mstSet);
mstSet[u] = true;
for (int v = 0; v < V; v++)
if (graph[u][v] && !mstSet[v] && graph[u][v] < key[v]) {
parent[v] = u;
key[v] = graph[u][v];
}
}
cout << "Edge Weight\n";
for (int i = 1; i < V; i++)
cout << parent[i] << " - " << i << " " << graph[i][parent[i]] << endl;
}
int main() {
int graph[V][V] = {
{0, 1, 3, 0},
{1, 0, 5, 2},
{3, 5, 0, 4},
{0, 2, 4, 0}
};
primMST(graph);
return 0;
}
import sys
V = 4
def min_key(key, mst_set):
min_val = sys.maxsize
min_index = -1
for v in range(V):
if not mst_set[v] and key[v] < min_val:
min_val = key[v]
min_index = v
return min_index
def prim_mst(graph):
key = [sys.maxsize] * V
parent = [-1] * V
mst_set = [False] * V
key[0] = 0
for _ in range(V - 1):
u = min_key(key, mst_set)
mst_set[u] = True
for v in range(V):
if graph[u][v] and not mst_set[v] and graph[u][v] < key[v]:
key[v] = graph[u][v]
parent[v] = u
print("Edge Weight")
for i in range(1, V):
print(f"{parent[i]} - {i} {graph[i][parent[i]]}")
graph = [
[0, 1, 3, 0],
[1, 0, 5, 2],
[3, 5, 0, 4],
[0, 2, 4, 0]
]
prim_mst(graph)
class PrimAlgorithm {
static final int V = 4;
int minKey(int key[], boolean mstSet[]) {
int min = Integer.MAX_VALUE, minIndex = -1;
for (int v = 0; v < V; v++)
if (!mstSet[v] && key[v] < min) {
min = key[v];
minIndex = v;
}
return minIndex;
}
void primMST(int graph[][]) {
int parent[] = new int[V];
int key[] = new int[V];
boolean mstSet[] = new boolean[V];
for (int i = 0; i < V; i++) {
key[i] = Integer.MAX_VALUE;
mstSet[i] = false;
}
key[0] = 0;
parent[0] = -1;
for (int count = 0; count < V - 1; count++) {
int u = minKey(key, mstSet);
mstSet[u] = true;
for (int v = 0; v < V; v++)
if (graph[u][v] != 0 && !mstSet[v] && graph[u][v] < key[v]) {
parent[v] = u;
key[v] = graph[u][v];
}
}
System.out.println("Edge Weight");
for (int i = 1; i < V; i++)
System.out.println(parent[i] + " - " + i + " " + graph[i][parent[i]]);
}
public static void main(String[] args) {
PrimAlgorithm obj = new PrimAlgorithm();
int graph[][] = {
{0, 1, 3, 0},
{1, 0, 5, 2},
{3, 5, 0, 4},
{0, 2, 4, 0}
};
obj.primMST(graph);
}
}
Edge Weight
0 - 1 1
1 - 3 2
0 - 2 3
Prim's Algorithm for extremely large graphs may be modified to work in parallel or distributed computing environments. Nevertheless, only a few parts of the algorithm (like updating minimum edge weights) can be parallelized efficiently. These methods are more sophisticated and are generally employed in high-performance computing situations.
Prim's Algorithm can have different performance depending on how the graph is represented and which data structure is used to select the minimum edge.
| Implementation Method | Time Complexity | Space Complexity | Explanation / When to Use |
|---|---|---|---|
| Adjacency Matrix | O(V²) | O(V²) | Each step scans all vertices to find the minimum edge. Best for dense graphs where most vertices are connected. |
| Adjacency List + Min-Heap (Priority Queue) | O(E log V) | O(E + V) | Efficiently selects the minimum edge using a heap. Best for sparse graphs and most real-world networks. |
| Adjacency List + Fibonacci Heap | O(E + V log V) | O(E + V) | Improves decrease-key operations. Mainly used for theoretical analysis, rarely in practice. |
Key Note:
Bottom Line: The same algorithm can be slow or fast depending on the data structure that is used; therefore, choose the data structure carefully.
Prim's Algorithm is a fundamental instrument in addressing real-world problems of the nature where one is required to connect multiple points with minimal total cost. Being efficient and greedy in nature, the algorithm is the most suitable choice in various domains to a great extent. These domains represent some of the most significant scenarios where Prim's Algorithm is meaningfully implemented:
Telecommunications and Internet Cabling:
One of the applications of Prim's Algorithm is in the design of layouts for cable installations (telephone lines, fiber optic cables, and internet backbones) that are cost-effective. The objective is to connect all users or stations with minimum total wiring cost and, at the same time, ensure full connectivity and no redundant loops.
Example: A telecommunications company wants to connect several cities with fiber optic cables. Each possible connection has an associated cost based on distance and terrain. By modeling this as a weighted graph and applying Prim's Algorithm, the company can determine the cheapest set of connections that link all cities.
Power Distribution Networks:
When planning the layout for electrical grids or circuit wiring, minimizing the amount of wire (and thus the cost and loss) is crucial. Prim's Algorithm helps design networks that connect all substations or components using the minimum total length of wire.
Example: An engineer designs the power lines needed to connect a group of substations, ensuring all are linked with the least amount of cable, reducing both installation and transmission losses.
Road, Railway, and Pipeline Networks:
The planning of the construction of roads, railways, or pipelines that connect several cities, factories, or distribution points is done by the use of Prim's Algorithm by governments and companies. The objective is to reduce the building costs as much as possible while keeping the system accessible.
Example: A logistics company needs to lay out new roads to connect warehouses in different regions. Using Prim's Algorithm ensures the network is fully connected with the least total road length.
LAN and WAN Setup:
Prim's Algorithm in computer networking is used to create local area networks (LANs) or wide area networks (WANs) that require the connection of all devices with the least possible cabling costs and without any redundant connections.
Hierarchical Clustering:
Prim's Algorithm is used in data science for hierarchical (agglomerative) clustering. By treating data points as nodes and distances as weights, the algorithm helps in grouping similar data points by constructing a minimum spanning tree that reveals natural clusters.
Procedural Content Generation:
Game developers and researchers use Prim's Algorithm to generate mazes and maps. By applying the algorithm to a grid graph with randomly assigned weights, it produces mazes with a single, unique path between any two points.
Example: The creation of this maze, which uses Prim's algorithm on a randomly weighted grid graph, is one of the numerous uses for Prim's method.
Water Supply and Irrigation Systems:
Designing the layout for water pipes or irrigation channels to connect all houses or fields while using the least amount of piping is another classic application.
Connecting Survey Points:
Surveyors use Prim's Algorithm to connect multiple geographical points (like mountain peaks or survey markers) with the shortest possible network, reducing costs and effort.
Minimum Spanning Tree (MST) problems can be solved using multiple algorithms. While Prim's Algorithm is one of the most popular, it is important to understand how it compares with other well-known approaches, such as Kruskal's, Borůvka's, and even why it is often confused with Dijkstra's Algorithm. Each algorithm follows a greedy algorithm strategy, but their behavior, efficiency, and use cases differ.
| Algorithm | Core Idea / Strategy | Graph Requirement | Greedy Approach | Handles Disconnected Graphs | Time Complexity | Memory Usage | Best Use Case / Notes |
|---|---|---|---|---|---|---|---|
| Prim's Algorithm (Prim–Jarník) | Grows MST from a starting vertex, adding the minimum edge that connects a new vertex | Connected, weighted graph | Yes | No | O(V²) (adjacency matrix) / O(E log V) (binary heap) | O(V) | Best for dense graphs and incremental growth from a vertex |
| Kruskal's Algorithm | Sorts all edges and adds them if they don't form a cycle | Weighted graph (connected or not) | Yes | Yes (forms minimum spanning forest) | O(E log E) | O(V) | Best for sparse graphs; uses Union-Find |
| Borůvka's Algorithm | Each vertex/component picks its cheapest outgoing edge | Weighted graph | Yes | Yes | O(E log V) | O(V) | Highly parallelizable; good for shared memory machines |
| Dijkstra's Algorithm | Expands shortest paths from a source vertex | Weighted graph (no negative edges) | Yes | No | O(E log V) | O(V) | Not an MST algorithm; solves shortest path problems |
| Parallel Prim's Algorithm | Parallel variant of Prim's using shared memory | Connected, weighted graph | Yes | No | Varies (hardware-dependent) | O(V) | Used in high-performance computing |
| Euclidean MST (EMST) | MST where edge weights are Euclidean distances | Points in geometric space | Yes | Depends on input | Varies | O(V) | Used for randomly distributed points and spatial graphs |
All MST algorithms are based on greedy principles, however, they vary in the way they choose edges and their size. Prim's Algorithm is best suited for dense, connected graphs, while Kruskal's is a good choice for sparse or disconnected graphs. Borůvka's is perfect for parallel environments, and Dijkstra's, although similar, is intended for shortest paths, not MST construction.
Prim's Algorithm is a fundamental tool for solving minimum spanning tree problems efficiently. By building the MST one node at a time and always choosing the minimum available edge, Prim's algorithm ensures optimality using a greedy approach.
With efficient implementations using heaps, the Prims Algorithm can solve massive MST problems in practical time, impacting areas ranging from network design to machine learning.
Mastering Prim's is essential to any one who is serious about data structures, algorithms, and computational problem-solving.
The Minimum Spanning Tree (MST) in a weighted, undirected graph may be found using Prim's Algorithm, a greedy technique. It adds the shortest edge connecting a vertex in the MST to a vertex outside the MST, starting at any random node and continuing until all vertices are included in the MST.
Prim's Algorithm gets its work done by the selection of a start node. Then, by adding the least edge that connects a vertex within the MST to a vertex outside the MST, the process is repeated until the MST contains all the vertices and the total edge weight is minimum.
The time complexity of the Prim's Algorithm is O(E logV) if a priority queue (min-heap) is used for the implementation. In this expression, E stands for the number of edges, and V is the number of vertices. This method is quite powerful for large graphs and works very well if the graph is dense and the correct data structure is used.
No, Prim's Algorithm requires the graph to be connected. If the graph is disconnected, it will only find the MST of the connected components. Each disconnected part would need to be processed separately.
Prim's and Kruskal's algorithms both attain the MST goal, but they think differently. With Prim's algorithm, the MST is constructed by adding edges from one vertex, whereas Kruskal's algorithm first orders all edges and then adds them one by one. Prim's is a good choice for dense graphs, while Kruskal's is better for sparse graphs.
In a typical situation, a priority queue (min-heap) is required in Prim's Algorithm so the smallest edge can be selected efficiently. Also, a set can be used to keep track of visited vertices, and an adjacency list or matrix can be used to represent the graph structure.
Prim's Algorithm is used in network design problems, such as designing the least-cost telecom or computer networks. It is also used in geographical mapping, electrical circuit design, and any application requiring an efficient way to connect all nodes with minimal total edge cost.
Source: NxtWave - CCBP Blog
Original URL: https://www.ccbp.in/blog/articles/prims-algorithm
Contact: [email protected] | +919390111761 (WhatsApp only)