Prim's algorithm grows a Minimum Spanning Tree one edge at a time. Starting from any vertex, it repeatedly adds the cheapest edge that connects a vertex in the tree to a vertex outside it. Using a min-heap, it runs in O(E log V). It is a greedy algorithm that produces the globally optimal MST.
int primsMST(vector<vector<pair<int,int>>>& adj, int n) {
vector<int> key(n,INT_MAX); vector<bool> inMST(n,false);
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<>> pq;
key[0]=0; pq.push({0,0}); int total=0;
while(!pq.empty()){
auto[w,u]=pq.top();pq.pop();
if(inMST[u])continue;
inMST[u]=true; total+=w;
for(auto[v,wt]:adj[u]) if(!inMST[v]&&wt<key[v]){key[v]=wt;pq.push({wt,v});}
}
return total;
}Prim's maintains a set of vertices in the MST and a priority queue of edges crossing the cut. At each step it picks the minimum-weight crossing edge, adding its endpoint to the MST.
The minimum-weight edge crossing any cut (partition of vertices into two sets) must be in some MST. This property proves Prim's greedy choice is always safe.
Prim's builds the MST vertex by vertex and is better for dense graphs. Kruskal's sorts all edges and adds them by weight, better for sparse graphs. Both produce a correct MST.
Quiz coming soon for this algorithm.