MST -- Prim's Algorithm

Quick Revisit

• USE WHEN: minimum spanning tree, especially with dense graphs or adjacency list input
• INVARIANT: always extend the tree by the minimum-weight edge crossing the cut (cut property)
• TIME: O((V + E) log V) with binary heap; O(V^2) with simple array for dense graphs | SPACE: O(V + E)
• CLASSIC BUG: not skipping already-finalized nodes when popping from the priority queue
• PRACTICE: ../12-practice-ladders/05-ladder-graphs.md

Grow a minimum spanning tree greedily from a single vertex, always attaching the cheapest edge that connects a new vertex. AL-19.

Difficulty: [Intermediate]Prerequisites: Graph Representation, Priority Queue and HeapsCF Rating: 1500-1800

---

Contents

• Intuition
• C++ STL Reference
• Implementation (Contest-Ready)
• Operations Reference
• Problem Patterns & Tricks
• Contest Cheat Sheet
• Gotchas & Debugging
• Common Mistakes
• Self-Test
• Practice Problems
• Recap
• Further Reading

---

Intuition

The Pain

We need a minimum spanning tree -- the same problem Kruskal solves. But Kruskal's first step is to sort every edge by weight. On a dense graph where $m\approx n^2$, that sort costs $O(n^2\log n)$, which dominates everything else. For a complete graph on $n=5000$ vertices we are sorting $\sim 12.5$ million edges -- painful and wasteful when most of those edges will never appear in the MST.

Can we avoid touching every edge up front? Can we grow the MST from a single starting node, discovering only the edges we need as we go?

The Key Insight

Grow the tree one node at a time: always attach the cheapest edge crossing the cut between the tree and the rest of the graph.

The image to keep is the cut, not the crystal. At any moment the vertices split into two groups: the ones already in the partial tree ($S$) and the ones still outside ($V\setminus S$). The "frontier" is the set of edges with one endpoint in each group. Prim's picks the cheapest such edge, pulls the outside endpoint into $S$, and repeats. After $n-1$ steps the cut is empty and every vertex is in the tree.

(A crystal-growth analogy is sometimes used because it captures "expand outward," but the correctness of the algorithm is the cut property, not the analogy. Mention the cut explicitly when explaining it to yourself.)

Dijkstra vs Prim — Same Heap, Different Meaning

The implementations look almost identical: both maintain a min-heap of candidate edges, both use a visited flag, both relax neighbours after popping. Confusing them is one of the most common mistakes for beginners and is worth resolving once.

	Dijkstra	Prim
What is in the heap key?	$d[u]$ — total cost from source to $u$	$w(u,v)$ — weight of one edge connecting $v$ to the tree
What does extracting do?	Finalise $u$ at distance $d[u]$	Add the cheapest cut edge to the tree
Relaxation condition	d[u] + w < d[v] (cumulative)	w < key[v] (single-edge)
Output	Shortest-path tree from a source	Minimum spanning tree
Cycle structure	Tree of paths	Tree of connections
Negative weights	Breaks correctness	Works fine — single-edge weights need no signedness assumption

The slogan: Dijkstra picks the closest unfinished node from the source; Prim picks the cheapest edge connecting any unfinished node to the current tree. Same heap, different meaning of "best."

If you are typing Dijkstra-flavoured code and the resulting tree weight seems off, the first thing to check is which of the two relaxation rules you wrote.

Visual Walkthrough

Graph:

       2         3
  (0)-----(1)-----(2)
   |     / |
   6   /8  5
   |  /    |
  (3)     (4)

  Edges: 0-1(2)  1-2(3)  0-3(6)  1-3(8)  1-4(5)
  V = 5, E = 5

Step 1 -- Seed vertex 0.

  Tree: {0}
  Frontier PQ: (w=2, to 1)  (w=6, to 3)

   [0]*
    |
    6
    |
   (3)         (1)        (2)        (4)

Step 2 -- Pop (w=2, v=1). Add edge 0--1, cost 2.

  Tree: {0, 1}        MST so far: 0--1 (2)
  Frontier PQ: (w=3, to 2)  (w=5, to 4)  (w=6, to 3)  (w=8, to 3)

        2
  [0]-----[1]
   |     /  |
   6   /8   5
   |  /     |
  (3)      (4)         (2)

Step 3 -- Pop (w=3, v=2). Add edge 1--2, cost 3.

  Tree: {0, 1, 2}     MST so far: 0--1 (2), 1--2 (3)
  Frontier PQ: (w=5, to 4)  (w=6, to 3)  (w=8, to 3)

        2        3
  [0]-----[1]-----[2]
   |     /  |
   6   /8   5
   |  /     |
  (3)      (4)

Step 4 -- Pop (w=5, v=4). Add edge 1--4, cost 5.

  Tree: {0, 1, 2, 4}  MST so far: 0--1 (2), 1--2 (3), 1--4 (5)
  Frontier PQ: (w=6, to 3)  (w=8, to 3)

        2        3
  [0]-----[1]-----[2]
   |        |
   6        5
   |        |
  (3)      [4]

Step 5 -- Pop (w=6, v=3). Add edge 0--3, cost 6.

  Tree: {0, 1, 2, 3, 4}  MST complete!
  Frontier PQ: (w=8, to 3) -- skipped, 3 already visited

        2        3
  [0]-----[1]-----[2]
   |        |
   6        5
   |        |
  [3]      [4]

  MST weight = 2 + 3 + 5 + 6 = 16
  Edge 1--3 (w=8) excluded.

  Legend:  [X] = in MST    (X) = not yet    * = seed

The Invariant

+------------------------------------------------------------------+
| INVARIANT                                                        |
|                                                                  |
| At every stage the edges chosen so far form a subset of some     |
| MST. The cheapest edge crossing the cut (tree, non-tree) is     |
| always safe to add.                                              |
|                                                                  |
| Proof sketch (Cut Property): Suppose the lightest cut edge e is  |
| NOT in an MST T*. Adding e to T* creates a cycle that crosses   |
| the cut at least twice; some other edge e' on that cycle also    |
| crosses the cut with w(e') >= w(e). Swapping e' for e gives a   |
| spanning tree of equal or lesser weight -- still an MST.         |
+------------------------------------------------------------------+

What the Code Won't Teach You

Prim's and Dijkstra look identical in code but compute different things.

Both use a min-heap, both have a "skip if visited" check, both relax neighbors. The critical difference is one line:

  Dijkstra relaxation:  if (d[u] + w < d[v])  d[v] = d[u] + w
                                ^
                            cumulative path cost

  Prim's relaxation:    if (w < key[v])        key[v] = w
                             ^
                         single edge weight only

Dijkstra accumulates the total distance from the source. Prim's only cares about the cheapest edge connecting a new node to the existing tree. Mix them up and you build a shortest-path tree instead of an MST -- a subtly different object that may have higher total edge weight.

The cut property is why the greedy choice works.

At every step, Prim's picks the lightest edge crossing the cut between "in-tree" and "not-in-tree" nodes. The cut property guarantees this edge belongs to some MST. Without understanding this, the algorithm feels like it "happens to work" -- understanding the cut property makes the correctness self-evident.

  MST so far (S)          Not yet in MST (T)
  +-----------+            +-----------+
  |           |  --w1-->   |           |
  |   nodes   |  --w2-->   |   nodes   |
  |  already  |  --w3-->   |   not yet |
  |  in tree  |            |  in tree  |
  +-----------+            +-----------+
       ^                        ^
       |   Cut edges: w1, w2, w3
       |   Prim's picks min(w1, w2, w3).
       |   Cut property: this edge is in some MST.
       +--- Why? If it weren't, adding it creates
            a cycle crossing the cut at least twice.
            Swap the heavier crossing edge -> lighter MST.

Dense Prim ($O(V^2)$) is the hidden weapon for complete graphs.

When $E=O(V^2)$, sorting all edges for Kruskal costs $O(V^2\log V)$. Dense Prim avoids the heap entirely -- a linear scan over $V$ nodes each round gives $O(V^2)$, which is optimal for complete graphs. This variant is rarely taught but frequently needed for geometric MST problems.

When to Reach for This

Trigger phrases in problem statements:

• "MST on a dense or complete graph" -- Dense Prim in $O(V^2)$ beats Kruskal's $O(V^2\log V)$.
• "Grow from a node" / "expand a connected component" -- Prim's vertex-centric growth is a natural fit.
• "Implicit edge weights" (e.g., all-pairs distances between coordinate points) -- Dense Prim computes weights on the fly without materializing an edge list.

Counter-examples (prefer Kruskal instead):

• Sparse graph ($m\approx n$) given as an edge list -- Kruskal with DSU is simpler and equally fast.
• Need to process edges in weight order for a non-MST reason -- Kruskal's sorted-edge view is more convenient.
• Union-Find is already built for the problem -- bolt-on Kruskal rather than adding a PQ.

---

C++ STL Reference

Function / Class	Header	What it does	Time
priority_queue<T, vector<T>, greater<>>	<queue>	Min-heap. Default PQ is max-heap; greater<> flips it.	--
pq.push({w, v})	<queue>	Insert element into heap	$O(\log n)$
pq.top()	<queue>	Access minimum element without removing	$O(1)$
pq.pop()	<queue>	Remove minimum element	$O(\log n)$
pq.empty()	<queue>	Check if heap is empty	$O(1)$
vector<vector<pair<int,int>>>	<vector>	Adjacency list: g[u] = {(v, w), ...}	--
auto [w, v] = pq.top();	--	Structured binding (C++17). Extracts both fields of pair.	--
pair<A,B> comparison	<utility>	Lexicographic: compares first, then second. Put weight first.	$O(1)$

---

Implementation (Contest-Ready)

Version 1: Minimal Contest Template

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

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<pair<int,int>>> g(n);
    for (int i = 0; i < m; i++) {
        int u, v, w; cin >> u >> v >> w; u--; v--;
        g[u].push_back({v, w});
        g[v].push_back({u, w});
    }
    vector<bool> vis(n);
    priority_queue<pair<long long,int>, vector<pair<long long,int>>, greater<>> pq;
    pq.push({0, 0});
    long long ans = 0;
    int cnt = 0;
    while (pq.size()) {
        auto [w, u] = pq.top(); pq.pop();
        if (vis[u]) continue;
        vis[u] = true;
        ans += w;
        cnt++;
        for (auto [v, wt] : g[u])
            if (!vis[v]) pq.push({wt, v});
    }
    cout << (cnt == n ? ans : -1) << "\n";
}

Version 2: Explained Version

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

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

    // Adjacency list: g[u] stores {neighbor, weight} pairs
    vector<vector<pair<int,int>>> g(n);
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        u--; v--;                             // convert to 0-indexed
        g[u].push_back({v, w});
        g[v].push_back({u, w});
    }

    vector<bool> vis(n, false);

    // Min-heap of (edge_weight, destination_vertex).
    // greater<> turns the default max-heap into a min-heap.
    // Weight goes first so pair comparison picks the lightest edge.
    priority_queue<pair<long long,int>,
                   vector<pair<long long,int>>,
                   greater<>> pq;

    // Seed vertex 0 with cost 0 (no edge to reach the start)
    pq.push({0LL, 0});
    long long total = 0;
    int added = 0;

    while (!pq.empty() && added < n) {
        auto [w, u] = pq.top();
        pq.pop();

        // Lazy deletion: if u is already in the MST, skip.
        // We may have pushed multiple entries for the same vertex.
        if (vis[u]) continue;

        vis[u] = true;
        total += w;
        added++;

        // Push all edges from u to vertices not yet in the MST
        for (auto [v, wt] : g[u]) {
            if (!vis[v]) {
                pq.push({(long long)wt, v});  // cast to avoid overflow
            }
        }
    }

    if (added < n) {
        cout << "IMPOSSIBLE\n";    // graph is disconnected
    } else {
        cout << total << "\n";
    }
}

Variant: Dense $O(V^2)$ Prim (No Heap)

Use when the graph is complete or near-complete ($E=\mathrm{\Theta }(V^2)$). Faster than heap-based Prim or Kruskal for $V\le 5000$ with $O(V^2)$ edges.

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    // Read or compute the full cost matrix
    vector<vector<long long>> cost(n, vector<long long>(n));
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            cin >> cost[i][j];

    const long long INF = 1e18;
    vector<long long> key(n, INF);  // min weight to attach v to MST
    vector<bool> vis(n, false);
    key[0] = 0;                     // start from vertex 0
    long long total = 0;

    for (int iter = 0; iter < n; iter++) {
        // Linear scan for unvisited vertex with smallest key
        int u = -1;
        for (int v = 0; v < n; v++)
            if (!vis[v] && (u == -1 || key[v] < key[u]))
                u = v;

        vis[u] = true;
        total += key[u];

        // Relax keys of u's neighbors
        for (int v = 0; v < n; v++)
            if (!vis[v] && cost[u][v] < key[v])
                key[v] = cost[u][v];
    }

    cout << total << "\n";
}

---

Operations Reference

Operation	Time	Space
Prim's (binary heap, sparse)	$O((V+E)\log V)$	$O(V+E)$
Prim's (dense, array scan)	$O(V^2)$	$O(V^2)$
Kruskal's (for comparison)	$O(E\log E)$	$O(V+E)$
Insert edge into PQ	$O(\log V)$	--
Extract-min from PQ	$O(\log V)$	--
Lazy-delete check (vis lookup)	$O(1)$	--

Choosing the right variant:

• Sparse ($E\approx V$): Heap-based Prim or Kruskal. Both $\approx O(V\log V)$.
• Dense ($E\approx V^2$): Dense Prim $O(V^2)$ beats Kruskal's $O(V^2\log V)$.
• Implicit complete graph (e.g., point distances): Dense Prim avoids materializing all $O(V^2)$ edges.

---

Problem Patterns & Tricks

Pattern 1: Direct MST Computation

Read a weighted undirected graph, output MST weight (or edges). Pure template.

// Run Version 1 from Section 4.
// Check cnt == n for connectivity.

Problems: CSES 1675 -- Minimum Spanning Tree

Pattern 2: Virtual / Auxiliary Node

Some vertices have a "standalone cost" $c_i$ (e.g., build a power station) vs. a "connection cost" $d_{ij}$ (e.g., lay cable between cities). Add a virtual node $s$ with edges $s\to i$ of weight $c_i$ for each $i$. MST of the augmented graph gives the optimal solution.

int total = n + 1;  // n real nodes + 1 virtual
vector<vector<pair<int,long long>>> g(total);
for (int i = 0; i < n; i++) {
    g[n].push_back({i, c[i]});   // virtual node n -> city i
    g[i].push_back({n, c[i]});
}
// Also add real edges between cities, then run Prim from node n

Problems: CF 1245D -- Shichikuji and Power Grid, CF 1095F -- Make It Connected

Pattern 3: Dense / Complete Graph MST

When $E=O(V^2)$ (e.g., distances between all pairs of coordinate points), sorting all edges for Kruskal costs $O(V^2\log V)$. Use the $O(V^2)$ dense Prim variant instead.

// Compute cost on the fly (e.g., Manhattan distance)
for (int i = 0; i < n; i++)
    for (int j = i + 1; j < n; j++)
        cost[i][j] = cost[j][i] = abs(x[i]-x[j]) + abs(y[i]-y[j]);
// Run dense Prim (Section 4 Variant)

Problems: CF 1245D, geometric MST problems

Pattern 4: MST Edge Analysis / Uniqueness

Classify each edge: always in every MST, in some but not all, or never in any MST. Build the MST, then for each non-MST edge $(u,v,w)$ find the maximum-weight edge on the MST path from $u$ to $v$. If that max equals $w$, the non-MST edge is interchangeable (some MST includes it).

// Build MST, root it.
// For each non-MST edge (u, v, w):
//   max_on_path = max edge weight on tree path u -> v (use LCA)
//   if max_on_path == w: edge is "replaceable"
//   if max_on_path >  w: impossible (MST property violated)
//   if max_on_path <  w: edge is never in any MST

Problems: CF 1108F -- MST Unification, CF 160D -- Edges in MST

Pattern 5: MST + Path Queries

Build the MST, then answer per-edge or per-query questions about tree paths. The maximum edge on the MST path between $u$ and $v$ equals the minimax path weight in the original graph. Combine MST with LCA + sparse table for $O(\log V)$ per query.

// Build MST -> root tree -> binary lifting with max-edge tracking
// Query: "MST weight if edge (u, v, w) must be included"
//   = mst_total - max_edge_on_path(u, v) + w

Problems: CF 609E -- Minimum spanning tree for each edge

---

Contest Cheat Sheet

+--------------------------------------------------------------+
|                   MST -- PRIM'S ALGORITHM                     |
+--------------------------------------------------------------+
| WHEN: "Connect all nodes at minimum cost"                     |
|   Dense / complete graph  -->  O(V^2) Prim (no heap)          |
|   Sparse graph            -->  heap Prim or Kruskal           |
|   Implicit edges          -->  O(V^2) Prim                    |
+--------------------------------------------------------------+
| HEAP-BASED (sparse):                                          |
|   priority_queue<pair<ll,int>,...,greater<>> pq;              |
|   pq.push({0, start});                                       |
|   while (pq.size()) {                                         |
|       auto [w, u] = pq.top(); pq.pop();                      |
|       if (vis[u]) continue;                                   |
|       vis[u] = 1; ans += w; cnt++;                            |
|       for (auto [v, wt] : g[u])                               |
|           if (!vis[v]) pq.push({wt, v});                      |
|   }                                                           |
+--------------------------------------------------------------+
| DENSE O(V^2): scan for min key[v] among unvisited, relax     |
+--------------------------------------------------------------+
| TIME:  O((V+E) log V) heap   |  O(V^2) dense                 |
| SPACE: O(V+E) heap           |  O(V^2) dense                 |
+--------------------------------------------------------------+
| TRAPS: greater<> for MIN-heap  |  long long for total weight  |
|        Check cnt == n for disconnected graphs                 |
+--------------------------------------------------------------+

---

Gotchas & Debugging

1. Max-heap vs. min-heap. priority_queue defaults to max-heap. You must pass greater<> as the third template argument. Forgetting this silently produces a maximum spanning tree.

2. Integer overflow. Weights up to ${10}^9$ with up to $2\times {10}^5$ edges means total MST weight can exceed $2^{31}-1$. Use long long for the accumulator. Cast weights when pushing: pq.push({(long long)wt, v}).

3. Disconnected graphs. Prim's only spans one component. After the loop, check added == n. If not, the MST doesn't exist.

4. 0-indexed vs. 1-indexed. Contest input usually uses 1-indexed vertices. Either subtract 1 when reading or allocate g(n + 1).

5. Lazy deletion PQ bloat. The heap can hold up to $O(E)$ entries (multiple entries per vertex). For $E\le 2\times {10}^5$ this is fine. For very large $E$, consider Kruskal or the eager key-decrease approach with an indexed PQ.

6. Self-loops. A self-loop $(u,u,w)$ gets pushed but is immediately discarded by the vis[u] check. No special handling needed.

7. Parallel edges. Multiple edges between the same pair work correctly -- the lighter one gets extracted first; heavier duplicates are skipped by lazy deletion.

8. Negative weights. Unlike Dijkstra, Prim's handles negative edge weights correctly. Negative edges are simply more attractive and get picked earlier.

9. Reconstructing MST edges. The minimal template only computes the total weight. To recover the tree, store parent information:

   // Push {weight, destination, source} into PQ
   // On extraction: parent[dest] = source
   vector<int> par(n, -1);
   // ... inside loop, when vis[u] is false:
   par[u] = source_vertex;

10. Dense variant initialization. Set key[start] = 0 and all others to INF before the loop. Forgetting this is a silent bug -- the algorithm won't grow from the start vertex.

Mental Traps

Trap 1: "I'll just use Dijkstra's code and change the problem to MST."

The heap, the visited check, and the neighbor loop are structurally the same. But the relaxation step is different, and confusing them produces a shortest-path tree, not an MST:

  Graph:  0 --10-- 1 --1-- 2
          |                 |
          +------5----------+

  Dijkstra from 0:                  Prim's from 0:
    d[0]=0                            key[0]=0
    d[1]=min(10, 5+1)=6              Extract 0: key[1]=10, key[2]=5
    d[2]=5                            Extract 2: key[1]=min(10,1)=1
    Path tree:                        Extract 1.
      0->2 (w=5), 2->1 (w=1)         MST edges:
      total weight = 6                 0-2 (w=5), 2-1 (w=1)
                                       total weight = 6

  Now with different weights:
  Graph:  0 --2-- 1 --8-- 2
          |                |
          +------9---------+

  Dijkstra from 0:                  Prim's from 0:
    d = [0, 2, 9]                    key = [0, 2, 8]
    Tree: 0->1 (w=2), 0->2 (w=9)    MST: 0-1 (w=2), 1-2 (w=8)
    total weight = 11                total weight = 10   <- DIFFERENT!
                                     MST picks the cheaper edge to 2
                                     even though the PATH is longer.

Trap 2: "Prim's handles disconnected graphs automatically."

Prim's only visits the component containing the start node. If the graph is disconnected, the remaining components are silently ignored:

  Component 1:  0 -- 1 -- 2      Component 2:  3 -- 4

  Prim's from node 0:
    Visits: {0, 1, 2}     cnt = 3
    Misses: {3, 4}         cnt < n = 5  ->  MST doesn't exist!

  FIX: After Prim's, check cnt == n.
       If cnt < n:
         Option A: report "IMPOSSIBLE" / "disconnected"
         Option B: run Prim's from each unvisited node
                   to get a minimum spanning FOREST

---

Common Mistakes

1. Not skipping already-finalized nodes. After popping from the priority queue, always check if (vis[u]) continue;. Without this, you process stale entries and may add wrong edges or do $O(E)$ extra work.

2. Confusing Prim with Dijkstra. Both use a min-heap and a visited check, but Prim relaxes by edge weight (if (w < key[v])), while Dijkstra relaxes by cumulative distance (if (d[u] + w < d[v])). Mix them up and you build a shortest-path tree, not an MST.

3. Using the priority queue version on dense graphs. When $E=O(V^2)$, heap operations cost $O(V^2\log V)$ total. The simple $O(V^2)$ array-scan Prim (no heap) is faster and simpler for complete or near-complete graphs.

---

Self-Test

Answer without looking at the code above.

• [ ] Prim's vs Dijkstra. Write the relaxation line for Prim's and for Dijkstra side by side. What is the key difference?
• [ ] Cut property. State the cut property of MSTs in one sentence. Explain why it guarantees Prim's greedy choice is correct.
• [ ] Dense variant. When is the $O(V^2)$ Prim's (no heap) faster than heap-based Prim's or Kruskal's? What type of graph triggers this?
• [ ] Disconnected check. After running Prim's, how do you detect that the graph is disconnected? Write the one-line check.
• [ ] Heap direction. What happens if you forget greater<> in the priority queue template? What kind of spanning tree do you get?

---

Practice Problems

#	Problem	Source	Difficulty	Key Idea
1	Minimum Spanning Tree	CSES 1675	Easy	Direct MST, template verification
2	Make It Connected	CF 1095F	Easy-Medium	Virtual node for per-vertex costs
3	MST Unification	CF 1108F	Medium	Count edges replaceable in MST
4	Shichikuji and Power Grid	CF 1245D	Medium	Virtual node + dense graph
5	GCD and MST	CF 1513D	Medium	MST with structured edge weights
6	Design Tutorial: Inverse the Problem	CF 472D	Medium-Hard	Build MST, verify distance matrix
7	Minimum spanning tree for each edge	CF 609E	Hard	MST + LCA path-max queries

---

Rating Progression

CF Rating	What You Should Be Comfortable With
1200	Template Prim's, compute MST weight on small graphs
1500	Prim's with priority queue, $O(n^2)$ Prim's for dense graphs, comparison with Kruskal
1800	Prim-like algorithms (e.g., "minimum cost to connect all nodes with special cost rules"), virtual nodes for modified MST
2100	Prim on implicit dense graphs (geometric MST), Prim + segment tree for specific structures

What Would You Do If...?

1. ...the graph is dense ($m\approx n^2$) and $n=5000$? Use the $O(n^2)$ version of Prim's (no priority queue, just scan all nodes for the minimum key). It's simpler and faster than the $O(m\log n)$ PQ version for dense graphs.

2. ...you need to find the MST of a complete geometric graph (points in 2D)? Naively, this has $O(n^2)$ edges. Use Prim's $O(n^2)$ directly, or use smarter geometric structures (Delaunay triangulation contains the MST and has only $O(n)$ edges).

3. ...some edges have equal weight and you need ANY valid MST? Both Prim's and Kruskal's handle ties arbitrarily. Any MST is valid -- you don't need to worry about tie-breaking unless the problem asks for a unique or lexicographically smallest MST.

The Mistake That Teaches

The bug: Your Prim's implementation produces a spanning tree, but it's not minimum -- the total weight is too high:

priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> pq;
pq.push({0, 0});
vector<int> key(n, INF);
vector<bool> in_mst(n, false);
key[0] = 0;
int total = 0;
while (!pq.empty()) {
    auto [w, u] = pq.top(); pq.pop();
    if (in_mst[u]) continue;
    in_mst[u] = true;
    total += w;
    for (auto [v, wt] : adj[u]) {
        if (!in_mst[v]) {
            pq.push({wt, v});  // always pushes, never checks key[v]
        }
    }
}

The lesson: This code works correctly! The if (in_mst[u]) continue; check handles stale entries. But it may be slow because it pushes many duplicate entries. The optimization: only push {wt, v} if wt < key[v], and update key[v] accordingly. This reduces PQ operations significantly.

Debug This

Bug 1: Prim's gives wrong MST weight:

priority_queue<pair<int,int>> pq;  // max-heap!
pq.push({0, start});

Answer

priority_queue<pair<int,int>> is a max-heap -- it extracts the most expensive edge first, producing a maximum spanning tree instead of a minimum one. Fix: use priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> for a min-heap.

Bug 2: $O(n^2)$ Prim's skips some nodes:

vector<int> key(n + 1, INF);
vector<bool> in_mst(n + 1, false);
key[1] = 0;
for (int iter = 0; iter < n; iter++) {
    int u = -1;
    for (int v = 1; v <= n; v++)
        if (!in_mst[v] && (u == -1 || key[v] < key[u]))
            u = v;
    in_mst[u] = true;
    for (auto [v, w] : adj[u]) {
        if (!in_mst[v] && w < key[v])
            key[v] = w;
    }
}
// Some nodes have key = INF at the end

Answer

If some nodes still have key = INF, the graph is disconnected -- those nodes are unreachable from node 1. Prim's cannot span disconnected components. Either the input graph is disconnected, or edges were not added in both directions for an undirected graph.

Bug 3: Prim's gives different MST weight than Kruskal's on the same graph:

// Kruskal: MST weight = 42
// Prim: MST weight = 45

Answer

Both algorithms should give the same MST weight (though possibly different edge sets if weights aren't unique). The likely bug is in Prim's implementation: either the adjacency list is built incorrectly (missing edges, wrong weights, directed instead of undirected), or the key/priority queue logic has an error. Debug by printing which edges each algorithm selects.

Historical Note

Prim's algorithm was first discovered by Vojtech Jarnik in 1930, independently rediscovered by Robert Prim in 1957, and again by Edsger Dijkstra in 1959. This is why it's sometimes called the Jarnik-Prim algorithm. Dijkstra's shortest-path algorithm (1959) is essentially the same structure with a different relaxation rule.

Recap

• Core idea: grow the MST from a seed vertex; always attach the cheapest edge crossing the cut between tree and non-tree nodes.
• Cut property guarantees the greedy choice is safe -- if the lightest cut edge were absent from the MST, swapping it in reduces (or preserves) total weight.
• Heap-based Prim: $O((V+E)\log V)$ -- best for sparse graphs with adjacency lists.
• Dense Prim (no heap): $O(V^2)$ -- optimal for complete/near-complete graphs; avoids materializing edges.
• Prim vs Kruskal: Prim is vertex-centric (grow from a node); Kruskal is edge-centric (sort and merge). Dense graphs favor Prim; sparse edge-list input favors Kruskal.
• Prim vs Dijkstra: identical code structure, but Prim relaxes by single edge weight, Dijkstra by cumulative path cost.
• Classic bugs: forgetting greater<> (max-heap instead of min-heap), not checking vis[u] after pop, integer overflow on total weight, not detecting disconnected graphs.

"Grow the tree: always grab the cheapest edge out."

---

Further Reading

• cp-algorithms -- Minimum spanning tree: Prim's algorithm
• cp-algorithms -- Minimum spanning tree: Kruskal's algorithm
• Codeforces EDU -- MST section
• See: 10-mst-kruskal.md -- Kruskal's with DSU, the other standard MST algorithm
• See: 01-graph-representation.md -- adjacency list / matrix fundamentals
• See: 07-dijkstra.md -- similar PQ-based greedy structure, shortest paths instead of MST