Prim's Algorithm (MST)

Concept

Prim's algorithm builds the MST by starting from one node and repeatedly adding the cheapest edge that connects a visited node to an unvisited node. It grows the tree one node at a time, always picking the minimum weight edge crossing the cut.

When to Use

  • ▸Minimum spanning tree on dense graphs (adjacency matrix)
  • ▸When the graph is given as an adjacency matrix
  • ▸Alternative to Kruskal when you prefer growing from a single source

Intuition

Start at any city. Look at all roads leaving your connected group of cities. Pick the cheapest one — it leads to a new city, add it to your group. Now look at all roads leaving the (larger) group, pick the cheapest to an unvisited city again. Repeat until all cities are in the group. This greedy approach always gives the MST.

Complexity

Time
O(V^2) with adjacency matrix, O(E log V) with priority queue
Space
O(V^2)

Template Code

cpp
#include<bits/stdc++.h>
using namespace std;

int find_min_key(vector<int> &key, vector<bool> &mstSet){
    int idx = -1;
    for(int i = 0; i < key.size(); i++){
        if(!mstSet[i] && (idx == -1 || key[i] < key[idx])) idx = i;
    }
    return idx;
}

int main(){
    ios_base::sync_with_stdio(0), cin.tie(0);

    int n, m;
    cin >> n >> m;

    const int inf = 1e9+7;
    vector<vector<int>> adj(n, vector<int>(n, inf));

    for(int i = 0; i < n; i++) adj[i][i] = 0;

    int u, v, w;
    for(int i = 0; i < m; i++){
        cin >> u >> v >> w;
        adj[u][v] = w;
        adj[v][u] = w;
    }

    vector<int> key(n, inf);
    vector<bool> mstSet(n, false);
    vector<int> parent(n);

    key[0] = 0;
    parent[0] = -1;

    for(int i = 0; i < n-1; i++){
        int u = find_min_key(key, mstSet);
        mstSet[u] = true;

        for(int v = 0; v < n; v++){
            if(!mstSet[v] && adj[u][v] < key[v]){
                key[v] = adj[u][v];
                parent[v] = u;
            }
        }
    }

    for(int i = 0; i < n; i++) cout << key[i] << " ";

    return 0;
}

// Sample Input:
// 5 7
// 0 1 2
// 0 2 3
// 1 2 1
// 1 3 4
// 2 3 5
// 2 4 6
// 3 4 7
//
// Sample Output (MST edge weights per node):
// 0 2 1 4 6