7. Prim's (MST)

Prim's Algorithm is used to find the Minimum Spanning Tree (MST) of a connected, undirected, weighted graph.

Use Prim's when

• Graph is already given as an adjacency list.
• You're comfortable with Priority Queues.
• Problems naturally describe "growing" a tree.

// Adjacency List
// adj[u] = { {neighbor, weight}, ... }
vector<vector<pair<int,int>>> adj(V);

for (auto edge : edges) {

    int u = edge[0];
    int v = edge[1];
    int wt = edge[2];

    adj[u].push_back({v, wt});
    adj[v].push_back({u, wt});   // Undirected graph
}

// Prim's Algorithm
vector<bool> visited(V, false);

// Min Heap
priority_queue<
    pair<int,int>,
    vector<pair<int,int>>,
    greater<pair<int,int>>
> pq;

// {edgeWeight, node}
pq.push({0, 0});

int mstWeight = 0;

while (!pq.empty()) {

    auto [weight, node] = pq.top();
    pq.pop();

    // Already included in MST
    if (visited[node])
        continue;

    visited[node] = true;

    // Add edge to MST
    mstWeight += weight;

    // Explore neighbors
    for (auto [neighbor, edgeWeight] : adj[node]) {

        if (!visited[neighbor]) {

            pq.push({edgeWeight, neighbor});
        }
    }
}

// mstWeight contains total weight of MST

Prim's with MST Edges

// {weight, node, parent}
priority_queue<
    vector<int>,
    vector<vector<int>>,
    greater<vector<int>>
> pq;

pq.push({0, 0, -1});

vector<pair<int,int>> mst;

int mstWeight = 0;

while (!pq.empty()) {

    auto current = pq.top();
    pq.pop();

    int weight = current[0];
    int node = current[1];
    int parent = current[2];

    if (visited[node])
        continue;

    visited[node] = true;
    mstWeight += weight;

    if (parent != -1)
        mst.push_back({parent, node});

    for (auto [neighbor, edgeWeight] : adj[node]) {

        if (!visited[neighbor]) {

            pq.push({edgeWeight, neighbor, node});
        }
    }
}