Prim's Algorithm — MST via Min-Heap Greedy Expansion

Algorithm

Start from vertex 0, add all its edges to a min-heap
Pop minimum edge (w, u, v)
If v is not visited: add to MST, push v's edges
Repeat until V vertices visited

Solutions

Python

import heapq

def prim(n, adj):
    visited = [False]*n
    heap = [(0, 0, -1)]
    total = 0
    mst = []
    while heap and len(mst) < n:
        w, u, parent = heapq.heappop(heap)
        if visited[u]: continue
        visited[u] = True
        total += w
        if parent != -1: mst.append((parent, u, w))
        for v, wt in adj[u]:
            if not visited[v]:
                heapq.heappush(heap, (wt, v, u))
    return total, mst

JavaScript

function prim(n, adj) {
    const vis=new Array(n).fill(false);
    const heap=[[0,0,-1]]; let total=0; const mst=[];
    const pop=()=>{let mi=0;for(let i=1;i<heap.length;i++)if(heap[i][0]<heap[mi][0])mi=i;const v=heap.splice(mi,1)[0];return v;};
    while(heap.length&&mst.length<n){
        const[w,u,p]=pop(); if(vis[u])continue; vis[u]=true; total+=w;
        if(p!==-1)mst.push([p,u,w]);
        for(const[v,wt]of adj[u])if(!vis[v])heap.push([wt,v,u]);
    }
    return[total,mst];
}

Java

import java.util.*;
public int prim(int n, List<int[]>[] adj) {
    boolean[] vis=new boolean[n];
    PriorityQueue<int[]> pq=new PriorityQueue<>(Comparator.comparingInt(a->a[0]));
    pq.offer(new int[]{0,0}); int total=0;
    while(!pq.isEmpty()){
        int[]top=pq.poll(); int w=top[0],u=top[1];
        if(vis[u])continue; vis[u]=true; total+=w;
        for(int[]nb:adj[u]) if(!vis[nb[0]]) pq.offer(new int[]{nb[1],nb[0]});
    }
    return total;
}

C++

#include <queue>
#include <vector>
using namespace std;
int prim(int n, vector<pair<int,int>> adj[]) {
    vector<bool> vis(n,false);
    priority_queue<pair<int,int>,vector<pair<int,int>>,greater<>> pq;
    pq.push({0,0}); int total=0;
    while(!pq.empty()){
        auto[w,u]=pq.top();pq.pop();
        if(vis[u])continue; vis[u]=true; total+=w;
        for(auto[v,wt]:adj[u]) if(!vis[v]) pq.push({wt,v});
    }
    return total;
}

C

/* C: adjacency matrix + key[] array Prim — O(V²) */
int prim_matrix(int g[][100], int n) {
    int key[100],inMST[100]; for(int i=0;i<n;i++){key[i]=INT_MAX;inMST[i]=0;}
    key[0]=0; int total=0;
    for(int iter=0;iter<n;iter++){
        int u=-1;
        for(int v=0;v<n;v++) if(!inMST[v]&&(u==-1||key[v]<key[u]))u=v;
        inMST[u]=1; total+=key[u];
        for(int v=0;v<n;v++) if(g[u][v]&&!inMST[v]&&g[u][v]<key[v])key[v]=g[u][v];
    }
    return total;
}