Skip to content

Minimum Spanning Tree (MST)

An MST of a connected weighted undirected graph is a subset of edges that connects all vertices with minimum total weight. Classic algorithms: Kruskal (sort edges, Union-Find) and Prim (grow tree with a priority queue).

Kruskal

Sort edges by weight; add edge (u,v) if it connects two different components.

#include <vector>
#include <algorithm>
using namespace std;

struct Edge { int u, v, w; };

int findSet(vector<int>& parent, int x) {
    return parent[x] == x ? x : parent[x] = findSet(parent, parent[x]);
}

bool unite(vector<int>& parent, vector<int>& rank, int a, int b) {
    a = findSet(parent, a); b = findSet(parent, 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<Edge>& edges) {
    sort(edges.begin(), edges.end(), [](const Edge& a, const Edge& b) { return a.w < b.w; });
    vector<int> parent(n), rankv(n, 0);
    for (int i = 0; i < n; i++) parent[i] = i;
    long long sum = 0;
    int cnt = 0;
    for (const Edge& e : edges) {
        if (unite(parent, rankv, e.u, e.v)) {
            sum += e.w;
            if (++cnt == n - 1) break;
        }
    }
    return cnt == n - 1 ? sum : -1; // -1 if disconnected
}

Prim (sketch)

Start from a root, repeatedly add the minimum-weight edge from the growing tree to a new vertex (dist[v] = min edge weight to attach v). Use a min-heap keyed by dist.

Complexity

  • Kruskal: \(O(E \log E)\) from sorting.
  • Prim: \(O(E \log V)\) with a binary heap.