Prim’s algorithm
Published by: Anil K. Panta
Prim’s Algorithm | Minimum Spanning Tree
Prim’s Algorithm is a popular Greedy Algorithm used to find the Minimum Spanning Tree (MST) for a weighted, connected, and undirected graph. The MST connects all vertices with the minimum total weight and no cycles.
What is Prim’s Algorithm?
Prim’s algorithm starts from any one vertex and grows the MST one edge at a time by selecting the minimum-weight edge that connects a vertex in the tree to a vertex outside the tree.
Steps of Prim’s Algorithm
Start with an empty MST.
Choose any starting vertex and add it to the MST.
From the MST, find the smallest edge that connects to a vertex not in MST.
Add that vertex and edge to the MST.
Repeat until all vertices are included.
Key Concepts:
Key array: Holds the minimum weight to reach a vertex.
Parent array: Stores the MST connections.
mstSet[]: Keeps track of vertices included in MST.
Prim’s Algorithm in C (Using Adjacency Matrix)
#include <stdio.h>
#include <limits.h>
#include <stdbool.h>
#define V 5 // Number of vertices
// Function to find the vertex with the minimum key value
int minKey(int key[], bool mstSet[]) {
int min = INT_MAX, min_index;
for (int v = 0; v < V; v++) {
if (mstSet[v] == false && key[v] < min) {
min = key[v], min_index = v;
}
}
return min_index;
}
// Function to print the constructed MST
void printMST(int parent[], int graph[V][V]) {
printf("Edge \tWeight\n");
for (int i = 1; i < V; i++) {
printf("%d - %d \t%d \n", parent[i], i, graph[parent[i]][i]);
}
}
// Function to construct MST using Prim's algorithm
void primMST(int graph[V][V]) {
int parent[V]; // Array to store constructed MST
int key[V]; // Key values to pick minimum weight edge
bool mstSet[V]; // To represent set of vertices included in MST
// Initialize all keys as INFINITE
for (int i = 0; i < V; i++) {
key[i] = INT_MAX;
mstSet[i] = false;
}
key[0] = 0; // Start from the first vertex
parent[0] = -1; // First node is always root of MST
for (int count = 0; count < V - 1; count++) {
int u = minKey(key, mstSet); // Pick the minimum key vertex
mstSet[u] = true; // Add it to MST set
// Update key and parent of adjacent vertices
for (int v = 0; v < V; v++) {
if (graph[u][v] && mstSet[v] == false && graph[u][v] < key[v]) {
parent[v] = u;
key[v] = graph[u][v];
}
}
}
printMST(parent, graph);
}
int main() {
int graph[V][V] = {
{ 0, 2, 0, 6, 0 },
{ 2, 0, 3, 8, 5 },
{ 0, 3, 0, 0, 7 },
{ 6, 8, 0, 0, 9 },
{ 0, 5, 7, 9, 0 }
};
primMST(graph);
return 0;
}
Output:
Edge Weight
0 - 1 2
1 - 2 3
0 - 3 6
1 - 4 5
This output shows the Minimum Spanning Tree edges and their weights.
Time and Space Complexity
Advantages of Prim’s Algorithm
Always finds a Minimum Spanning Tree.
Easy to implement.
Efficient with dense graphs when used with priority queues.
Disadvantages:
Less efficient on sparse graphs unless optimized.
Requires additional space for priority queues.
Starting vertex may affect output (when multiple MSTs exist).
Prim’s vs Kruskal’s Algorithm
Final Thought:
Prim’s Algorithm builds the MST starting from a single vertex, adding the smallest adjacent edge at each step — making it perfect for dense, connected graphs.
