Skip to content

Minimum Spanning Trees

The Problem

You are given a weighted, undirected graph with \(n\) nodes and \(m\) edges. Find a spanning tree — a subset of edges that connects all nodes — with the minimum total edge weight.

A spanning tree of \(n\) nodes has exactly \(n - 1\) edges and no cycles. Among all possible spanning trees, the one with the smallest sum of edge weights is the Minimum Spanning Tree (MST).

The Greedy Choice: At every step, pick the cheapest available edge that does not create a cycle. This locally cheapest choice is globally optimal because of the cut property: for any partition of the nodes into two groups, the lightest edge crossing the partition must belong to some MST.

Both Kruskal's and Prim's algorithms exploit this property — they just apply it in different orders.

Why Brute Force Fails

Without cycle detection, you would simply take the \(n - 1\) cheapest edges. But cheap edges can form cycles, wasting slots. In the example graph below, edges 1--3 (weight 1), 4--5 (weight 2), and 1--2 (weight 3) are the three cheapest. If the fourth cheapest is 2--3 (weight 5), adding it creates a cycle \(1 - 2 - 3 - 1\) and leaves node 6 disconnected. You need Union-Find (or equivalent) to skip cycle-forming edges and ensure every added edge actually connects a new component.

Kruskal's Algorithm

Idea: Sort all edges by weight. Scan them from lightest to heaviest. For each edge, add it to the MST if it connects two different components. Skip it if it would create a cycle.

To check whether two nodes are already connected, use Union-Find (Disjoint Set Union). This data structure supports two operations:

  • findRoot(node): return the representative (root) of the component containing node.
  • uniteComponents(nodeA, nodeB): merge the two components. Return true if they were separate (edge is useful), false if they were already connected (edge would create a cycle).

With path compression and union by rank, both operations run in nearly \(O(1)\) amortized time — specifically \(O(\alpha(n))\), where \(\alpha\) is the inverse Ackermann function.

Overall complexity: \(O(m \log m)\) for sorting, plus \(O(m \cdot \alpha(n))\) for the union-find operations. The sort dominates.

Kruskal Trace

Kruskal's algorithm: sort edges by weight, add if no cycle, skip otherwise

Consider this 6-node graph:

Nodes: 1, 2, 3, 4, 5, 6

Edges:
  1--2  weight 3
  1--3  weight 1
  2--3  weight 5
  2--4  weight 4
  3--5  weight 6
  4--5  weight 2
  4--6  weight 7
  5--6  weight 8

After sorting edges by weight: \((1,3,1),\ (4,5,2),\ (1,2,3),\ (2,4,4),\ (2,3,5),\ (3,5,6),\ (4,6,7),\ (5,6,8)\).

We need \(n - 1 = 5\) edges for the MST.

Step Edge Weight Creates Cycle? Action Components
1 1–3 1 No Add {1,3}, {2}, {4}, {5}, {6}
2 4–5 2 No Add {1,3}, {2}, {4,5}, {6}
3 1–2 3 No Add {1,2,3}, {4,5}, {6}
4 2–4 4 No Add {1,2,3,4,5},
5 2–3 5 Yes (both in {1,2,3,4,5}) Skip {1,2,3,4,5},
6 4–6 7 No Add {1,2,3,4,5,6}

MST edges: 1–3, 4–5, 1–2, 2–4, 4–6. Total weight = \(1 + 2 + 3 + 4 + 7 = 17\).

Notice that edge 2–3 (weight 5) was skipped because nodes 2 and 3 were already connected through node 1. Edge 3–5 (weight 6) and 5–6 (weight 8) were never even reached — we already had 5 edges.

Kruskal Code

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int numNodes, numEdges;
    cin >> numNodes >> numEdges;

    vector<tuple<long long, int, int>> edgeList(numEdges);
    for (int i = 0; i < numEdges; i++) {
        int nodeA, nodeB;
        long long edgeWeight;
        cin >> nodeA >> nodeB >> edgeWeight;
        edgeList[i] = {edgeWeight, nodeA, nodeB};
    }

    sort(edgeList.begin(), edgeList.end());

    vector<int> parentNode(numNodes + 1);
    vector<int> treeRank(numNodes + 1, 0);
    iota(parentNode.begin(), parentNode.end(), 0);

    function<int(int)> findRoot = [&](int node) -> int {
        if (parentNode[node] != node)
            parentNode[node] = findRoot(parentNode[node]);
        return parentNode[node];
    };

    auto uniteComponents = [&](int nodeA, int nodeB) -> bool {
        int rootA = findRoot(nodeA);
        int rootB = findRoot(nodeB);
        if (rootA == rootB) return false;
        if (treeRank[rootA] < treeRank[rootB]) swap(rootA, rootB);
        parentNode[rootB] = rootA;
        if (treeRank[rootA] == treeRank[rootB]) treeRank[rootA]++;
        return true;
    };

    long long totalMSTWeight = 0;
    int edgesUsed = 0;

    for (auto& [mstEdgeWeight, nodeA, nodeB] : edgeList) {
        if (uniteComponents(nodeA, nodeB)) {
            totalMSTWeight += mstEdgeWeight;
            edgesUsed++;
            if (edgesUsed == numNodes - 1) break;
        }
    }

    if (edgesUsed == numNodes - 1)
        cout << totalMSTWeight << "\n";
    else
        cout << "IMPOSSIBLE\n";

    return 0;
}

Key points:

  • Edges are stored as (weight, nodeA, nodeB) so the default tuple comparison sorts by weight first.
  • findRoot uses path compression: every node on the path to the root gets directly attached to the root.
  • uniteComponents uses union by rank: the shorter tree is attached under the taller tree, keeping the structure flat.
  • We break early once \(n - 1\) edges are collected.
  • If the graph is disconnected, edgesUsed < numNodes - 1 and we output IMPOSSIBLE.

Prim's Algorithm

Idea: Start from any node. Maintain a set of nodes already in the MST. At each step, add the cheapest edge that connects a node inside the MST to a node outside the MST. Repeat until all nodes are included.

Use a min-heap of (weight, node) pairs. When you pop the cheapest entry, if that node is already in the MST, skip it. Otherwise, add it and push all its neighbors into the heap.

Overall complexity: \(O(m \log m)\) with a binary heap, or \(O(m + n \log n)\) with a Fibonacci heap (rarely used in competitive programming).

Prim Trace

Same graph as before. Start from node 1.

Step Pop from Heap Weight Already in MST? Action MST Nodes Push Neighbors
0 (0, 1) 0 No Add node 1 {1} (3,2), (1,3)
1 (1, 3) 1 No Add node 3 {1,3} (5,2), (6,5)
2 (3, 2) 3 No Add node 2 {1,2,3} (4,4)
3 (4, 4) 4 No Add node 4 {1,2,3,4} (2,5), (7,6)
4 (2, 5) 2 No Add node 5 {1,2,3,4,5} (8,6)
5 (5, 2) 5 Yes Skip {1,2,3,4,5} —
6 (6, 5) 6 Yes Skip {1,2,3,4,5} —
7 (7, 6) 7 No Add node 6 {1,2,3,4,5,6} —

MST edges added with weights: \(1 + 3 + 4 + 2 + 7 = 17\). Same total as Kruskal's — both find an MST.

Notice Prim's explores the graph outward from a starting node, while Kruskal's processes edges globally by weight. They reach the same result because of the cut property.

Prim Code

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int numNodes, numEdges;
    cin >> numNodes >> numEdges;

    vector<vector<pair<long long, int>>> adjacencyList(numNodes + 1);
    for (int i = 0; i < numEdges; i++) {
        int nodeA, nodeB;
        long long edgeWeight;
        cin >> nodeA >> nodeB >> edgeWeight;
        adjacencyList[nodeA].push_back({edgeWeight, nodeB});
        adjacencyList[nodeB].push_back({edgeWeight, nodeA});
    }

    vector<bool> inMST(numNodes + 1, false);
    long long totalMSTWeight = 0;
    int edgesUsed = 0;

    auto heapComparator = [](pair<long long, int>& left, pair<long long, int>& right) {
        return left.first > right.first;
    };

    priority_queue<pair<long long, int>,
                   vector<pair<long long, int>>,
                   decltype(heapComparator)> minHeap(heapComparator);

    minHeap.push({0, 1});

    while (!minHeap.empty() && edgesUsed < numNodes) {
        auto [mstEdgeWeight, currentNode] = minHeap.top();
        minHeap.pop();

        if (inMST[currentNode]) continue;

        inMST[currentNode] = true;
        totalMSTWeight += mstEdgeWeight;
        edgesUsed++;

        for (auto& [neighborWeight, neighborNode] : adjacencyList[currentNode]) {
            if (!inMST[neighborNode]) {
                minHeap.push({neighborWeight, neighborNode});
            }
        }
    }

    if (edgesUsed == numNodes)
        cout << totalMSTWeight << "\n";
    else
        cout << "IMPOSSIBLE\n";

    return 0;
}

Key points:

  • The adjacency list stores (weight, neighbor) pairs, matching the heap's format.
  • The lambda heapComparator makes the priority queue a min-heap (smallest weight on top).
  • We push (0, 1) to start from node 1 with zero cost — this initial node contributes no edge weight.
  • The inMST check after popping handles stale heap entries: a node might be pushed multiple times with different weights, but only the first pop (cheapest) matters.
  • edgesUsed counts nodes added to the MST. We need all \(n\) nodes (including the start node with weight 0).

Why Greedy Works — The Cut Property

Both algorithms are correct because of one fundamental theorem.

Cut Property: For any cut \((S, V \setminus S)\) of the graph — any partition of nodes into two non-empty groups — the minimum-weight edge crossing the cut is safe to include in some MST.

Proof sketch: Suppose edge \(e = (u, v)\) is the minimum-weight edge crossing a cut, but some MST \(T\) does not include \(e\). Add \(e\) to \(T\). This creates a cycle. That cycle must cross the cut at least twice (it goes from \(u\)'s side to \(v\)'s side and back). So there's another edge \(f\) in the cycle that also crosses the cut. Since \(e\) is the minimum crossing edge, \(w(e) \leq w(f)\). Remove \(f\) from \(T \cup \{e\}\). The result is still a spanning tree, and its weight is \(\leq w(T)\). So \(T' = T \cup \{e\} \setminus \{f\}\) is also an MST that includes \(e\). \(\square\)

How Kruskal's exploits the cut property: When Kruskal's considers edge \((u, v)\) and \(u, v\) are in different components, define \(S\) = the component containing \(u\). Edge \((u, v)\) crosses this cut, and it's the minimum-weight crossing edge (all lighter edges were processed earlier and either added or were internal to components). By the cut property, \((u, v)\) is safe.

How Prim's exploits the cut property: At each step, define \(S\) = the set of nodes already in the MST. The edge popped from the min-heap is the cheapest edge from \(S\) to \(V \setminus S\). By the cut property, it's safe.

Kruskal vs Prim

Kruskal's Prim's
Approach Global: sort all edges, process lightest first Local: grow MST from a starting node
Data structure Union-Find Min-heap + adjacency list
Complexity \(O(m \log m)\) \(O(m \log m)\) with binary heap
Best for Sparse graphs (\(m \approx n\)) Dense graphs (\(m \approx n^2\))
Edge list input Natural fit (edges already listed) Needs adjacency list conversion
Multiple components Handles naturally (forest) Needs to restart from unvisited nodes
Implementation Simpler (sort + union-find) More bookkeeping (heap + visited array)

Rule of thumb: In competitive programming, Kruskal's is the default choice. It's shorter to code, works directly with edge lists, and handles disconnected graphs. Use Prim's when the graph is dense or when you're given an adjacency matrix.

Try It

The starter code has Kruskal's framework with the cycle-check logic left empty. Fill in the findRoot and uniteComponents functions, then use them in the loop. The snippet shows the Union-Find pattern.

Test on the example graph:

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

Output:
17

Disconnected graph (no spanning tree):

Input:
4 2
1 2 5
3 4 3

Output:
IMPOSSIBLE

Single node:

Input:
1 0

Output:
0

Predict before running: What happens if you feed a graph where all edge weights are equal? How many valid MSTs exist for a complete graph on 4 nodes with all weights = 1?

Problems

Problem Link Difficulty
CSES — Road Reparation cses.fi/problemset/task/1675 Easy
CF 1513D — GCD and MST codeforces.com/contest/1513/problem/D 1700
CF 609E — Minimum Spanning Tree For Each Edge codeforces.com/contest/609/problem/E 1900
CSES — New Roads Queries cses.fi/problemset/task/2101 Medium
Kattis — Min Spanning Tree open.kattis.com/problems/minspantree Easy
LC 1167 — Min Cost to Connect Sticks leetcode.com/problems/minimum-cost-to-connect-sticks Medium
LC 743 — Network Delay Time leetcode.com/problems/network-delay-time Medium
LC 1584 — Min Cost to Connect All Points leetcode.com/problems/min-cost-to-connect-all-points Medium