Prim’s algorithm is a greedy algorithm that finds a Minimum Spanning Tree (MST) for a weighted, connected, undirected graph. A spanning tree connects all the vertices of a graph with no cycles; the minimum spanning tree is the one whose total edge weight is the smallest possible. Prim’s builds this tree one vertex at a time, always adding the cheapest edge that connects a new vertex to the tree already built.
How Prim’s Algorithm Works
- Start from any vertex and mark it as visited (part of the tree).
- Look at all edges that connect a visited vertex to an unvisited vertex.
- Pick the edge with the smallest weight and add the new vertex to the tree.
- Repeat until every vertex is in the tree (i.e. you have added
n − 1 edges).
Because it always grows the tree by the locally cheapest edge, Prim’s is a textbook example of the greedy strategy.
The Program
This clean, portable version uses an adjacency (cost) matrix. A weight of 0 in the input means “no edge”, which we treat as infinity (INF):
#include <stdio.h>
#define INF 999
#define MAX 20
int main(void)
{
int cost[MAX][MAX];
int visited[MAX] = {0};
int n, i, j;
int ne = 1; /* edges added so far */
int mincost = 0; /* total weight of the MST */
printf("Enter the number of nodes : ");
scanf("%d", &n);
printf("Enter the adjacency (cost) matrix:\n");
for (i = 1; i <= n; i++)
for (j = 1; j <= n; j++) {
scanf("%d", &cost[i][j]);
if (cost[i][j] == 0)
cost[i][j] = INF; /* no direct edge */
}
visited[1] = 1; /* start building the tree from node 1 */
printf("\nEdges in the Minimum Spanning Tree:\n");
while (ne < n) {
int min = INF, a = 0, b = 0;
/* Find the cheapest edge from a visited node to an unvisited node. */
for (i = 1; i <= n; i++)
if (visited[i])
for (j = 1; j <= n; j++)
if (!visited[j] && cost[i][j] < min) {
min = cost[i][j];
a = i;
b = j;
}
if (a == 0) /* no edge found — graph is disconnected */
break;
printf("Edge %d : (%d - %d) cost = %d\n", ne++, a, b, min);
mincost += min;
visited[b] = 1;
}
printf("\nMinimum cost of the spanning tree = %d\n", mincost);
return 0;
}
How the Program Works
- The graph is stored as an
n × n cost matrix. Any 0 entered is replaced by INF (999) to mean “these two nodes are not directly connected”.
- We start with node 1 marked visited, then loop until we have added
n − 1 edges.
- On each pass the nested loops scan every edge that goes from a visited node to an unvisited node and remember the cheapest one (
a → b).
- That edge is printed, its cost is added to
mincost, and node b is marked visited so it becomes part of the growing tree.
- If no such edge exists, the graph is disconnected and the loop stops safely.
This modernised version removes the old void main(), <conio.h>, clrscr() and getch() calls from the original textbook code — none of those are standard C, and the program now compiles cleanly with GCC, Clang or any standard compiler.
Sample Output
Enter the number of nodes : 3
Enter the adjacency (cost) matrix:
0 2 0
2 0 3
0 3 0
Edges in the Minimum Spanning Tree:
Edge 1 : (1 - 2) cost = 2
Edge 2 : (2 - 3) cost = 3
Minimum cost of the spanning tree = 5
Time Complexity
| Implementation |
Time Complexity |
Best for |
| Adjacency matrix (this program) |
O(V²) |
Dense graphs, easy to understand |
| Adjacency list + min-heap |
O(E log V) |
Sparse graphs, large inputs |
For a solid foundation in graph algorithms and the C used to implement them, The C Programming Language by Kernighan and Ritchie is the classic reference — find it on Amazon.
This post contains affiliate links. If you buy through them, we may earn a small commission at no extra cost to you.
Related C Programs
To run this without setting up a compiler, paste it into one of the best online C compilers. For a permanent local toolchain, follow our guide to a complete C development environment.
