Prim's Algorithm
Prim's algorithm builds a Minimum Spanning Tree by greedily expanding from a starting vertex, always picking the minimum cost edge to an unvisited vertex.
Introduction
Prim's Algorithm is a greedy algorithm that finds the Minimum Spanning Tree (MST) of a connected, undirected, weighted graph. Unlike Kruskal's which sorts all edges, Prim's grows the MST one vertex at a time — starting from any vertex and always selecting the minimum weight edge connecting the current MST to a new vertex.
Problem Statement
Given a connected undirected weighted graph, find a subset of edges forming a tree that includes every vertex, where the total weight is minimized.
Real World Applications
- → Designing minimum cost network topologies
- → Approximating Travelling Salesman Problem solutions
- → Creating maze generation algorithms
- → Telecommunications network layout
- → Power grid design
Algorithm Explanation
Prim's starts with an arbitrary vertex and maintains two sets: vertices already in the MST and those not yet included. At each step, it finds the minimum weight edge connecting the MST set to a vertex outside it, adds that vertex to the MST, and updates the minimum costs. This continues until all vertices are included.
Step-by-Step Procedure
- 1 Start with vertex 1. Mark it as visited. Set lowcost[i] = weight(1, i) for all other vertices.
- 2 Find the unvisited vertex v with minimum lowcost value.
- 3 Mark v as visited and add edge (u[v], v) to the MST.
- 4 Update lowcost for all unvisited vertices: if weight(v, j) < lowcost[j], update lowcost[j] = weight(v, j) and u[j] = v.
- 5 Repeat steps 2-4 until all vertices are visited.
- 6 Print all MST edges and total minimum cost.
Complete C Program
#include <stdio.h>
#include <stdlib.h>
#define INFI 99
int edges[10][10], n, wt[10][10];
void prims() {
int u[10], lowcost[10], visited[10];
int min, mincost = 0, i, j, v;
visited[1] = 1;
for(i = 2; i <= n; i++) {
visited[i] = 0;
u[i] = 1;
lowcost[i] = wt[1][i];
}
for(i = 1; i <= n - 1; i++) {
min = lowcost[2];
v = 2;
for(j = 3; j <= n; j++) {
if(lowcost[j] < min) {
min = lowcost[j];
v = j;
}
}
edges[i][1] = u[v];
edges[i][2] = v;
mincost += lowcost[v];
visited[v] = 1;
lowcost[v] = INFI;
for(j = 2; j <= n; j++) {
if(wt[v][j] < lowcost[j] && !visited[j]) {
lowcost[j] = wt[v][j];
u[j] = v;
}
}
}
printf("Edges of Minimum Spanning Tree:\n");
for(i = 1; i <= n - 1; i++)
printf("(%d %d) ", edges[i][1], edges[i][2]);
printf("\nMinimum Cost: %d\n", mincost);
}
int main() {
int i, j;
printf("Enter the Number of Vertices: ");
scanf("%d", &n);
printf("Enter the Cost Matrix:\n");
for(i = 1; i <= n; i++)
for(j = 1; j <= n; j++)
scanf("%d", &wt[i][j]);
prims();
return 0;
}Sample Input & Output
4
99 10 6 5
10 99 99 15
6 99 99 4
5 15 4 99Edges of Minimum Spanning Tree:
(1 4) (4 3) (1 2)
Minimum Cost: 19Dry Run / Trace
Start at vertex 1. lowcost = [∞, 99, 10, 6, 5] Iter 1: min = lowcost[4]=5, add edge (1,4), cost=5. Update lowcost. Iter 2: min = lowcost[3]=4 (via vertex 4), add edge (4,3), cost=9. Iter 3: min = lowcost[2]=10, add edge (1,2), cost=19. Total MST cost = 19.
Advantages & Disadvantages
✓ Advantages
- + Efficient for dense graphs (many edges)
- + No need to sort all edges globally
- + Works well with adjacency matrix representation
- + Easy to implement
✗ Disadvantages
- − O(V²) complexity — slower than Kruskal's for sparse graphs
- − Requires the graph to be connected
- − Must restart from scratch if the graph changes
Viva Questions & Answers
Q1. What is the difference between Kruskal's and Prim's algorithm?
Kruskal's sorts all edges and picks globally minimum edges avoiding cycles. Prim's grows the MST from a starting vertex, always picking the minimum edge to an unvisited vertex.
Q2. What data structure makes Prim's algorithm O(E log V)?
Using a min-heap (priority queue) instead of scanning all vertices reduces complexity to O(E log V).
Q3. Is Prim's algorithm a greedy algorithm?
Yes, at each step it greedily selects the minimum weight edge connecting the current MST to a new vertex.
Q4. What is the lowcost array in Prim's algorithm?
lowcost[i] stores the minimum weight edge connecting vertex i to the current MST. It is updated as new vertices are added.
Q5. Can Prim's algorithm work on directed graphs?
Prim's algorithm is designed for undirected graphs. For directed graphs, different algorithms like Edmonds' algorithm are used.