Prim’s Algorithm in C – Minimum Spanning Tree (MST)

Prim’s algorithm finds the Minimum Spanning Tree (MST) of a weighted undirected graph — the set of edges that connects all vertices at the lowest possible total cost. It works by growing a single tree: start at any vertex, then repeatedly add the cheapest edge that reaches a vertex not yet in the tree, until all vertices are included. This page gives a working C implementation, a step-by-step trace showing exactly which edge is chosen at each step, and a clear explanation of how Prim’s compares to Dijkstra’s and Kruskal’s.

What Is a Minimum Spanning Tree?

A spanning tree of a graph with V vertices is any set of V−1 edges that connects all vertices with no cycles. There can be many spanning trees. The minimum spanning tree is the one with the smallest sum of edge weights.

How Prim’s Algorithm Works — Step by Step

Same 5-vertex graph used in the Dijkstra’s algorithm post:

Edges: 0-1(4), 0-4(8), 1-2(8), 1-4(11), 2-3(7), 3-4(9)

Adjacency matrix:
     0   1   2   3   4
0  [ 0   4   0   0   8 ]
1  [ 4   0   8   0  11 ]
2  [ 0   8   0   7   0 ]
3  [ 0   0   7   0   9 ]
4  [ 8  11   0   9   0 ]

key[v] = cheapest edge weight connecting v to the current MST. Starts at INF for all except vertex 0 (key=0).

MST edges chosen: 0–1 (weight 4), 1–2 (weight 8), 2–3 (weight 7), 0–4 (weight 8). Total MST cost = 27.

C Program: Prim’s Algorithm

/* Prim's Minimum Spanning Tree algorithm
 * Compile: gcc -ansi -Wall -Wextra prims.c -o prims */
#include <stdio.h>
#define MAX 10
#define INF 1000000

/* Return the vertex not yet in the MST with the smallest key value.
   key[v] is the cheapest edge weight that can pull v into the tree. */
int min_key(int key[], int in_mst[], int n)
{
    int i, min_idx = -1;
    int min = INF;
    for (i = 0; i < n; i++) {
        if (!in_mst[i] && key[i] < min) {
            min = key[i];
            min_idx = i;
        }
    }
    return min_idx;
}

void prim(int graph[][MAX], int n)
{
    int key[MAX], parent[MAX], in_mst[MAX];
    int i, j, u, total = 0;

    for (i = 0; i < n; i++) {
        key[i]    = INF;
        in_mst[i] = 0;
        parent[i] = -1;
    }
    key[0] = 0;           /* start growing the MST from vertex 0 */

    for (i = 0; i < n - 1; i++) {
        u = min_key(key, in_mst, n);
        if (u == -1) break;       /* graph is disconnected */
        in_mst[u] = 1;

        for (j = 0; j < n; j++) {
            if (graph[u][j] > 0 && !in_mst[j] &&
                graph[u][j] < key[j]) {
                key[j]    = graph[u][j];
                parent[j] = u;
            }
        }
    }

    printf("MST Edge        Weight\n");
    printf("----------      ------\n");
    for (i = 1; i < n; i++) {
        if (parent[i] == -1)
            printf("  vertex %d unreachable\n", i);
        else {
            printf("  %d -- %d          %d\n",
                   parent[i], i, graph[parent[i]][i]);
            total += graph[parent[i]][i];
        }
    }
    printf("----------      ------\n");
    printf("Total MST cost: %d\n", total);
}

int main(void)
{
    int graph[MAX][MAX];
    int n, i, j;

    printf("Enter number of vertices (2-%d): ", MAX);
    if (scanf("%d", &n) != 1 || n < 2 || n > MAX) {
        printf("Invalid.\n"); return 1;
    }
    printf("Enter %dx%d adjacency matrix (0 = no edge, undirected):\n", n, n);
    for (i = 0; i < n; i++)
        for (j = 0; j < n; j++)
            if (scanf("%d", &graph[i][j]) != 1) {
                printf("Invalid.\n"); return 1;
            }

    printf("\nPrim's Minimum Spanning Tree:\n");
    printf("==============================\n");
    prim(graph, n);
    return 0;
}

Sample Output

Enter number of vertices (2-10): 5
Enter 5x5 adjacency matrix (0 = no edge, undirected):
0 4 0 0 8
4 0 8 0 11
0 8 0 7 0
0 0 7 0 9
8 11 0 9 0

Prim's Minimum Spanning Tree:
==============================
MST Edge        Weight
----------      ------
  0 -- 1          4
  1 -- 2          8
  2 -- 3          7
  0 -- 4          8
----------      ------
Total MST cost: 27

Code Explanation

• key[] array: Records the cheapest known edge weight that can pull each vertex into the growing MST. Starts at INF for all vertices except vertex 0, which gets key[0]=0 to seed the algorithm. As the MST grows and new vertices become reachable, their key values are updated to the weight of the cheapest connecting edge.
• in_mst[]: Tracks which vertices have been permanently added to the MST. Once a vertex joins the MST, its key value is finalized and it is never reconsidered.
• parent[]: For each vertex, records which already-in-MST vertex provided its cheapest connecting edge. After the algorithm finishes, iterating over parent[1..n-1] gives the complete list of MST edges: edge i is parent[i]–i with weight graph[parent[i]][i].
• min_key(): Linear scan returning the non-MST vertex with the smallest key. O(V) per call × V calls = O(V²) total — the same complexity as Dijkstra’s with linear scan.
• Update condition graph[u][j] < key[j]: When vertex u joins the MST, check every neighbour j. If the direct edge u–j is cheaper than j’s current best connection to the MST, update key[j] and parent[j]. Note there is no need to check key[u] != INF here (unlike Dijkstra) because we look at the raw edge weight, not a cumulative path sum.
• Disconnected graph: If min_key() returns -1, the remaining vertices cannot be reached from the current MST. The loop breaks and those vertices will show “unreachable” in the output — you have a spanning forest, not a tree.

Prim’s vs Dijkstra’s — Key Difference

The two algorithms look almost identical in code but solve different problems:

The critical difference: Dijkstra relaxes using the accumulated distance from the source; Prim’s relaxes using only the direct edge weight. This is why Prim’s produces a minimum-cost tree rather than shortest paths.

Prim’s vs Kruskal’s for MST

Frequently Asked Questions

Related Programs

• Dijkstra’s Algorithm in C – Shortest Path
• BFS in C – Breadth-First Search
• DFS in C – Depth-First Search
• Floyd-Warshall Algorithm in C

Recommended books:
The C Programming Language — K&R (India) |
(US)
 | 
C Programming: A Modern Approach — K.N. King (India) |
(US)

Practice graph algorithm questions: C Aptitude Questions — or try our C Programming Quiz App on Android.