Prim’s Algorithm in C, C++, Java & Python – Code with Explanation & Examples in Short and Simple

   

C Program

#include <stdio.h>
#define INF 9999
int main() {
    int n = 4, g[4][4] = {
        {0, 1, 3, INF},
        {1, 0, 2, 4},
        {3, 2, 0, 5},
        {INF, 4, 5, 0}
    };
    int vis[4] = {0}, cost = 0, i, j;
    vis[0] = 1;
    for (int e = 0; e < n - 1; e++) {
        int min = INF, x = 0, y = 0;
        for (i = 0; i < n; i++)
            if (vis[i])
                for (j = 0; j < n; j++)
                    if (!vis[j] && g[i][j] && g[i][j] < min)
                        min = g[i][j], x = i, y = j;
        vis[y] = 1; cost += min;
        printf("%d-%d (%d)\n", x, y, min);
    }
    printf("Total cost: %d", cost);
}

C Output

Input:
Graph with 4 nodes and weights:
0-1(1), 0-2(3), 1-2(2), 1-3(4), 2-3(5)
Output:
Input: Adjacency Matrix

Output:
0-1 (1)
1-2 (2)
1-3 (4)
Total cost: 7

C++ Program

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n = 5;
    int g[5][5] = {
        {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}
    };
    vector<int> vis(n), key(n, INT_MAX), par(n, -1);
    key[0] = 0;
    for (int c = 0; c < n; c++) {
        int u = -1;
        for (int i = 0; i < n; i++) if (!vis[i] && (u == -1 || key[i] < key[u])) u = i;
        vis[u] = 1;
        for (int v = 0; v < n; v++)
            if (g[u][v] && !vis[v] && g[u][v] < key[v])
                key[v] = g[u][v], par[v] = u;
    }
    for (int i = 1; i < n; i++)
        cout << par[i] << "-" << i << " (" << g[i][par[i]] << ")\n";
}

C++ Output

Input:
Graph with 5 vertices
Edges: 0-1(2), 0-3(6), 1-2(3), 1-4(5), 2-4(7), 3-4(9)
Output:
Input: Adjacency Matrix

Output:
0-1 (2)
1-2 (3)
0-3 (6)
1-4 (5)

JAVA Program

import java.util.*;
class Main {
    public static void main(String[] args) {
        int n = 4;
        int[][] g = {{0, 10, 6, 0}, {10, 0, 5, 15}, {6, 5, 0, 4}, {0, 15, 4, 0}};
        boolean[] vis = new boolean[n];
        int[] key = new int[n], par = new int[n];
        Arrays.fill(key, Integer.MAX_VALUE);
        key[0] = 0; par[0] = -1;
        for (int c = 0; c < n; c++) {
            int u = -1;
            for (int i = 0; i < n; i++)
                if (!vis[i] && (u == -1 || key[i] < key[u])) u = i;
            vis[u] = true;
            for (int v = 0; v < n; v++)
                if (g[u][v] != 0 && !vis[v] && g[u][v] < key[v]) {
                    par[v] = u;
                    key[v] = g[u][v];
                }
        }
        for (int i = 1; i < n; i++)
            System.out.println(par[i] + "-" + i + " (" + g[i][par[i]] + ")");
    }
}

JAVA Output

Input:
Graph edges: 0-1(10), 0-2(6), 1-2(5), 1-3(15), 2-3(4)
Output:
Input: Adjacency Matrix

Output:
0-2 (6)
2-3 (4)
2-1 (5)

Python Program

import heapq
g = {0: [(1, 2), (3, 6)], 1: [(0, 2), (2, 3), (4, 5)],
     2: [(1, 3), (4, 7)], 3: [(0, 6), (4, 9)], 4: [(1, 5), (2, 7), (3, 9)]}
n, vis, mst = 5, set(), []
q = [(0, 0, -1)]  # (weight, u, parent)
while q and len(vis) < n:
    w, u, p = heapq.heappop(q)
    if u in vis: continue
    vis.add(u)
    if p != -1: mst.append((p, u, w))
    for v, wt in g[u]:
        if v not in vis:
            heapq.heappush(q, (wt, v, u))
for u, v, w in mst: print(f"{u}-{v} ({w})")

Python Output

Input:
Graph edges: 0-1(2), 0-3(6), 1-2(3), 1-4(5), 2-4(7), 3-4(9)
Output:
Input: Adjacency list

Output:
0-1 (2)
1-2 (3)
1-4 (5)
0-3 (6)

In-Depth Explanation

Example

In the C example, the graph:

0-1 (1), 0-2 (3), 1-2 (2), 1-3 (4), 2-3 (5)

Prim's Algorithm begins at node 0, selecting the smallest weight edge that connects a new node.

It inserts:

0-1 (1)

1-2 (2)

1-3 (4)

Total cost = 7

Real-Life Analogy

Suppose we are constructing a road network between cities. You begin in one city and always grow out to the closest unlinked city at cheapest cost. You repeat this until all cities are linked — the very thing that Prim's Algorithm does. It's analogous to expanding a tree from a single root, branching only when it's lowest cost.

Why It Matters

Prim's Algorithm is one of the two main MST algorithms (the other being Kruskal's).

It's:

Greedy, always picking the lowest-cost edge

Excellent when the graph is dense and presented through adjacency matrix

Prevents cycles by linking new nodes only

Used in:

Network cable optimization

Telecom tower linkages

Electricity/water pipe layout planning

Learning Insights

You learn:

How MSTs provide minimum cost spanning structure

How greedy algorithms can provide global optima

Utilization of priority queues or arrays to manage minimum edge weights

You also observe the distinction between Prim's vertex-based expansion and Kruskal's edge-based selection.

Interview & Real-World Use

Prim's is a well-known question in:

Graph optimization

MST construction

System design concerning connectivity

Applied in:

Urban infrastructure

Telecom cable planning

Real-time navigation systems

Game map generation

Prim's Algorithm is a must-know in graph theory, assisting you in constructing cost-effective connection structures between nodes. For networks, pipelines, or transport systems, Prim's approach of selecting the most affordable connection at every step results in a globally optimal solution. With working and brief code in C, C++, Java, and Python, you can observe how efficient and versatile this algorithm can be in competitive programming and practical systems. Familiarity with Prim's provides a strong basis for addressing graph-based problems in technical interviews as well as infrastructure designing.