C Program to find a minimum spanning tree using Prim’s algorithm

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

1. Start from any vertex and mark it as visited (part of the tree).
2. Look at all edges that connect a visited vertex to an unvisited vertex.
3. Pick the edge with the smallest weight and add the new vertex to the tree.
4. 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

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

• C Program for Dijkstra’s Shortest Path Algorithm
• C Program to Implement Breadth First Search (BFS)
• C Program to Implement Depth First Search (DFS)
• Complete List of 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.