Prim's MST

Minimum spanning tree using priority queue — greedy cut-based approach in O(E log V).

[Graph]|

Jul 9, 2026

|explanatory_notes.md|

#prim#mst#minimum-spanning-tree#greedy

$cat source_code/

cpp

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pli = pair<ll, int>;

const int MAXN = 2e5 + 5;
vector<pair<int, ll>> adj[MAXN];
bool inMST[MAXN];

ll prim(int root, int n) {
    ll cost = 0;
    priority_queue<pli, vector<pli>, greater<pli>> pq;
    pq.push({0, root});
    while (!pq.empty()) {
        auto [w, u] = pq.top(); pq.pop();
        if (inMST[u]) continue;
        inMST[u] = true;
        cost += w;
        for (auto &[v, wt] : adj[u])
            if (!inMST[v]) pq.push({wt, v});
    }
    return cost;
}

23 linesutf-8

$cat explanation_notes.md

notes_viewer --renderedmarkdown (math enabled)

Prim's MST

Greedy algorithm that grows the MST one edge at a time, always picking the cheapest edge crossing the cut.

How It Works

Start from any root node, push it to a min-priority queue with cost

0

Pop the cheapest edge. If the destination is already in the MST, skip it

Otherwise, add it to the MST, accumulate its cost, and push all its unvisited neighbors

When to Use

Dense graphs where

E \approx V^2

(Prim outperforms Kruskal here)

When you need the MST cost or MST edges

Alternative: Kruskal with DSU is often simpler for sparse graphs

Complexity

Time —

O(E \log V)

with binary heap

Space —

O(V + E)