Skip to content

Kruskal's and Prim's

Every Graph Has a Cheapest Skeleton

Take any connected weighted graph. Strip away edges until only a tree remains, but keep the total weight as small as possible. That tree is the Minimum Spanning Tree. It connects every node with the cheapest possible set of N-1 edges. Two classical algorithms find it: one grows a forest from sorted edges, the other grows a single tree from a starting node.

What Is an MST?

Given a connected undirected graph with N nodes and M weighted edges, a spanning tree uses exactly N-1 edges and connects all nodes. The minimum spanning tree is the one with the smallest total edge weight.

If the graph is disconnected, no spanning tree exists. You get a minimum spanning forest instead -- one MST per connected component.

Kruskal's Algorithm

Kruskal's algorithm: sort edges by weight, add if no cycle via DSU

Idea: Sort all edges by weight. Greedily add each edge if it connects two different components.

Steps:

  1. Sort edges by weight (ascending).
  2. Initialize a DSU with N singletons.
  3. For each edge (u, v, w) in sorted order: if find(u) != find(v), add the edge and unite(u, v).
  4. Stop after adding N-1 edges.
#include <bits/stdc++.h>
using namespace std;

int par[200005], rnk[200005];

int find(int x) {
    return par[x] == x ? x : par[x] = find(par[x]);
}

void unite(int a, int b) {
    a = find(a); b = find(b);
    if (a == b) return;
    if (rnk[a] < rnk[b]) swap(a, b);
    par[b] = a;
    if (rnk[a] == rnk[b]) rnk[a]++;
}

int main() {
    int n, m;
    cin >> n >> m;
    vector<tuple<int,int,int>> edges(m);
    for (auto& [w, u, v] : edges) cin >> u >> v >> w;
    sort(edges.begin(), edges.end());

    for (int i = 1; i <= n; i++) { par[i] = i; rnk[i] = 0; }

    long long cost = 0;
    int cnt = 0;
    for (auto& [w, u, v] : edges) {
        if (find(u) != find(v)) {
            unite(u, v);
            cost += w;
            if (++cnt == n - 1) break;
        }
    }

    if (cnt < n - 1) cout << "IMPOSSIBLE\n";
    else cout << cost << "\n";
}

Complexity: O(E log E) for sorting + O(E * alpha(N)) for DSU operations. Total: O(E log E).

💡 Key insight. Kruskal's works on an edge list. It never builds an adjacency list. This makes it ideal for sparse graphs or problems that hand you edges directly.

Prim's Algorithm

Prim's algorithm: grow MST from a starting node using priority queue

Idea: Start from any node. Repeatedly add the cheapest edge that connects a tree node to a non-tree node.

Steps:

  1. Start with node 1 in the MST. Push all its edges into a min-heap.
  2. Pop the cheapest edge. If the destination is already in the MST, skip it.
  3. Otherwise, add the destination to the MST and push its edges.
  4. Repeat until the MST has N nodes.
#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<pair<int,int>>> adj(n + 1);
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }

    vector<bool> inMST(n + 1, false);
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> pq;
    pq.push({0, 1});
    long long cost = 0;
    int cnt = 0;

    while (!pq.empty() && cnt < n) {
        auto [w, u] = pq.top(); pq.pop();
        if (inMST[u]) continue;
        inMST[u] = true;
        cost += w;
        cnt++;
        for (auto [v, wt] : adj[u])
            if (!inMST[v]) pq.push({wt, v});
    }

    if (cnt < n) cout << "IMPOSSIBLE\n";
    else cout << cost << "\n";
}

Complexity: O((V + E) log V) with a binary heap. Each edge is pushed at most once.

💡 Key insight. Prim's looks exactly like Dijkstra's. The only difference: Dijkstra pushes {dist_to_v, v}, Prim's pushes {edge_weight, v}. Prim's doesn't accumulate distances.

When to Use Which

Criterion Kruskal's Prim's
Graph density Sparse (E close to V) Dense (E close to V^2)
Input format Edge list Adjacency list
Data structure DSU Priority queue
Complexity O(E log E) O((V+E) log V)
Parallelism Edge-independent Grows from one root

For competitive programming, Kruskal's is the default. It's shorter to code, works on edge lists, and the DSU template is reusable. Prim's wins when the graph is dense or when you already have an adjacency list.

Full Trace: Kruskal's on a 5-Node Graph

Graph edges: (1,2,4), (1,3,1), (2,3,3), (2,4,2), (3,4,5), (3,5,6), (4,5,7).

Sorted by weight: (1,3,1), (2,4,2), (2,3,3), (1,2,4), (3,4,5), (3,5,6), (4,5,7).

Step Edge Weight find(u)==find(v)? Action Components
1 1-3 1 No Add {1,3} {2} {4} {5}
2 2-4 2 No Add {1,3} {2,4} {5}
3 2-3 3 No Add {1,2,3,4}
4 1-2 4 Yes Skip {1,2,3,4}
5 3-4 5 Yes Skip {1,2,3,4}
6 3-5 6 No Add {1,2,3,4,5}

MST edges: 1-3, 2-4, 2-3, 3-5. Total weight: 1 + 2 + 3 + 6 = 12. Four edges for five nodes.

⚠ Gotcha. Store edges as (weight, u, v) so that sorting by the tuple's natural order sorts by weight first. If you store (u, v, weight), you sort by endpoint IDs.

CSES Road Reparation

Problem: N cities, M roads with repair costs. Find the minimum total cost to make all cities reachable from each other. Print "IMPOSSIBLE" if the graph is disconnected.

This is a direct MST problem. Use Kruskal's.

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

int par[200005], rnk[200005];

int find(int x) {
    return par[x] == x ? x : par[x] = find(par[x]);
}

void unite(int a, int b) {
    a = find(a); b = find(b);
    if (a == b) return;
    if (rnk[a] < rnk[b]) swap(a, b);
    par[b] = a;
    if (rnk[a] == rnk[b]) rnk[a]++;
}

int main() {
    int n, m;
    cin >> n >> m;
    vector<tuple<int,int,int>> edges(m);
    for (auto& [w, u, v] : edges) cin >> u >> v >> w;
    sort(edges.begin(), edges.end());
    for (int i = 1; i <= n; i++) { par[i] = i; rnk[i] = 0; }

    long long cost = 0;
    int cnt = 0;
    for (auto& [w, u, v] : edges) {
        if (find(u) != find(v)) {
            unite(u, v);
            cost += w;
            if (++cnt == n - 1) break;
        }
    }

    if (cnt < n - 1) cout << "IMPOSSIBLE\n";
    else cout << cost << "\n";
}

The only twist is detecting disconnection. If we add fewer than N-1 edges, the graph has no spanning tree.

Try It

The starter code has DSU ready. Add the edge-sorting and greedy selection logic.

Test case 1: 

Input:
5 6
1 2 3
2 3 5
2 4 2
3 4 8
5 1 7
5 4 4

Output:
14

Test case 2: 

Input:
4 2
1 2 5
3 4 3

Output:
IMPOSSIBLE

Challenge: Solve the same problem with Prim's. Compare the code length.

Problems

Problem Link Difficulty
CSES Road Reparation cses.fi/problemset/task/1675 Easy
LC 1135 — Connecting Cities With Minimum Cost leetcode.com/problems/connecting-cities-with-minimum-cost Medium
LC 1584 — Min Cost to Connect All Points leetcode.com/problems/min-cost-to-connect-all-points Medium