Minimum Spanning Tree

What Is a Minimum Spanning Tree?

Given a connected, undirected, weighted graph G = (V, E), a Minimum Spanning Tree (MST) is a subset of edges that connects all vertices with the smallest possible total edge weight, without forming any cycle. An MST always contains exactly V − 1 edges.

Two fundamental properties guarantee the correctness of every greedy MST algorithm:

• Cut property — For any cut of the graph, the lightest edge crossing the cut belongs to some MST. This justifies greedily picking the cheapest crossing edge.
• Cycle property — For any cycle in the graph, the heaviest edge in the cycle does not belong to any MST (assuming unique edge weights). This justifies discarding expensive edges that close a cycle.

If all edge weights are distinct, the MST is unique. When duplicate weights exist, multiple MSTs may share the same total cost.

Kruskal’s Algorithm

Kruskal’s algorithm sorts all edges by weight and greedily adds each edge that does not create a cycle. A Disjoint Set Union (DSU / Union-Find) data structure tracks connected components so that the cycle check runs in near-constant time.

Sort edges by weight
mst = []
for each edge (u, v, w) in sorted order:
    if find(u) != find(v):
        union(u, v)
        mst.append((u, v, w))
    if |mst| == V - 1: break

Let’s trace Kruskal’s on this 6-node graph. Edges sorted by weight: (1,2):1, (3,4):2, (0,2):3, (3,5):4, (2,4):5, (1,3):6, (0,1):7, (4,5):8.

Prim’s Algorithm

Prim’s algorithm grows the MST from a single source vertex. At each step it picks the lightest edge crossing the cut between the tree and the remaining vertices, using a min-heap.

visited[src] = true
pq.push({0, src})

while pq is not empty:
    (w, u) = pq.extractMin()
    if visited[u]: continue
    visited[u] = true
    mst_weight += w
    for each edge (u, v, cost):
        if not visited[v]:
            pq.push({cost, v})

Tracing Prim’s on the same graph starting from node 0:

Both Kruskal’s and Prim’s produce the same total weight of 15. The MST edges are: (1,2), (3,4), (0,2), (3,5), (2,4).

Borůvka’s Algorithm

Borůvka’s algorithm (1926) is the oldest MST algorithm and is naturally parallelizable. In each phase, every connected component independently selects its lightest outgoing edge. All selected edges are added simultaneously, and the process repeats until only one component remains.

while number_of_components > 1:
    for each component C:
        find lightest edge leaving C
    add all such edges to MST
    merge components

Each phase at least halves the number of components, so there are at most O(log V) phases. Each phase scans all edges in O(E), giving total time O(E log V). This algorithm is especially useful in parallel/distributed settings and forms the basis of randomised linear-time MST algorithms.

Interactive Animation

Second-Best MST & Uniqueness

MST Uniqueness

An MST is unique if and only if, for every non-tree edge, it is strictly heavier than every other edge on the cycle it would form with the MST. If any non-tree edge ties with the heaviest tree edge on its cycle, a second MST of equal cost exists.

Second-Best MST

The second-best MST differs from the MST in exactly one edge swap: remove one tree edge and add one non-tree edge. The efficient approach:

1. Build the MST.
2. For each pair of vertices (u, v), precompute the maximum edge weight on the MST path from u to v using LCA with sparse table — O(V log V) preprocessing, O(1) per query.
3. For each non-tree edge (u, v, w), the cost of swapping is MST_weight − maxEdge(u,v) + w. Take the minimum over all non-tree edges.

Overall complexity: O(E log V).

C++ Implementation

Kruskal’s with DSU

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

struct DSU {
    vector<int> parent, rank_;
    DSU(int n) : parent(n), rank_(n, 0) {
        iota(parent.begin(), parent.end(), 0);
    }
    int find(int x) {
        return parent[x] == x ? x : parent[x] = find(parent[x]);
    }
    bool unite(int a, int b) {
        a = find(a); b = find(b);
        if (a == b) return false;
        if (rank_[a] < rank_[b]) swap(a, b);
        parent[b] = a;
        if (rank_[a] == rank_[b]) rank_[a]++;
        return true;
    }
};

long long kruskal(int n, vector<array<int,3>>& edges) {
    sort(edges.begin(), edges.end(),
         [](auto& a, auto& b){ return a[2] < b[2]; });
    DSU dsu(n);
    long long cost = 0;
    int cnt = 0;
    for (auto& [u, v, w] : edges) {
        if (dsu.unite(u, v)) {
            cost += w;
            if (++cnt == n - 1) break;
        }
    }
    return cnt == n - 1 ? cost : -1; // -1 if disconnected
}

Prim’s with Priority Queue

long long prim(int n, const vector<vector<pair<int,int>>>& adj) {
    vector<bool> vis(n, false);
    // {weight, vertex}
    priority_queue<pair<int,int>, vector<pair<int,int>>,
                   greater<pair<int,int>>> pq;
    pq.push({0, 0});
    long long cost = 0;
    int cnt = 0;

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

Complexity Analysis

Kruskal’s is the most popular choice in competitive programming. Sorting dominates at O(E log E) = O(E log V) since E ≤ V². The DSU operations are nearly O(1) amortized with path compression and union by rank.

Prim’s with a binary heap is preferable when the graph is given as an adjacency list and is dense (E ≈ V²), because Kruskal’s sorting step becomes expensive.

Practice Problems

1. LeetCode 1584. Min Cost to Connect All Points — Classic MST on coordinate plane
2. CSES. Road Reparation — Standard MST, detect disconnected graph
3. Codeforces 609E. Minimum Spanning Tree For Each Edge — MST + LCA path max query
4. Codeforces 472D. Design Tutorial: Inverse the Problem — Build MST, verify distance matrix
5. SPOJ. MST — Large-scale minimum spanning tree
6. LeetCode 1135. Connecting Cities With Minimum Cost — Direct Kruskal / Prim application

Summary

• An MST connects all vertices with minimum total edge weight using exactly V − 1 edges.
• Kruskal’s: sort edges, greedily add non-cycle edges using DSU. O(E log E). Best for sparse graphs and edge-list input.
• Prim’s: grow tree from a source via min-heap. O((V+E) log V). Best for dense graphs with adjacency lists.
• Borůvka’s: parallel component-wise lightest-edge selection. O(E log V). Best for parallel settings.
• The cut property and cycle property underpin all greedy MST algorithms.
• Second-best MST can be found in O(E log V) by precomputing path maxima with LCA.