xiii. Minimum Spanning Trees

The cut property (the lightest edge across any cut is in some MST) and the cycle property (the strictly heaviest edge on any cycle is in no MST) justify Kruskal ($O(m\log m)$), Prim ($O(m\log n)$, or $O(n^2)$ for dense graphs) and Borůvka ($O(m\log n)$, and the method of choice for implicit complete graphs). The MST also minimises the maximum edge on every path between two vertices (bottleneck paths), which is why MST + path-max queries solve many “minimise the largest edge” problems.

Proof: cut and cycle properties, uniqueness, bottleneck paths

Cut: let $e$ be a lightest edge across cut $(S,\bar{S})$ and $T$ an MST without $e$. $T+e$ has a cycle crossing the cut at another edge $f$ with $w(f)\ge w(e)$; $T+e-f$ is a spanning tree of weight $\le w(T)$, hence an MST containing $e$. Cycle: if the strictly heaviest edge $e$ of a cycle were in an MST $T$, removing it splits $T$ into two sides; the cycle crosses that cut at another, lighter edge $f$, and $T-e+f$ is lighter: contradiction. Uniqueness: with distinct weights, two different MSTs $T_1,T_2$ would have a lightest edge $e$ in their symmetric difference, say in $T_1$; $T_2+e$ has a cycle containing an edge $f\notin T_1$ with $w(f)>w(e)$ (by minimality of $e$ and distinctness), and $T_2+e-f$ is lighter than $T_2$. Bottleneck: for $u,v$ and the MST path between them with maximum edge $e$, any $u$–$v$ path crosses the cut obtained by deleting $e$ from the MST, at some edge $f$; by the cut property argument $w(f)\ge w(e)$ (else swapping would lighten the MST).

Ties change what "second-best" means

With duplicate weights, “strictly greater total weight” and “any spanning tree different from the MST” are different targets. secondBestMST above tracks both the maximum ($m_1$) and the second-largest distinct value ($m_2$) on each tree path so it can answer either: compare the swapped-in edge against $m_1$ for “strictly greater,” or fall back to $m_2$ when a same-weight swap (a genuinely different tree, same total cost) is what the problem wants.

Kruskal, Prim, Borůvka

ll kruskal(int n, vector<array<ll, 3>> E, vector<array<ll, 3>>* tree = nullptr) {   // {w, u, v}
    sort(all(E)); vector<int> d(n); iota(all(d), 0);
    auto f = [&](int x) { while (d[x] != x) x = d[x] = d[d[x]]; return x; };
    ll tot = 0;
    for (auto& e : E) { int a = f(e[1]), b = f(e[2]); if (a != b) { d[a] = b; tot += e[0]; if (tree) tree->push_back(e); } }
    return tot;
}
ll primDense(const vector<vector<ll>>& w) {                // adjacency matrix, INF = no edge; O(n^2)
    int n = sz(w); const ll INF = LLONG_MAX / 4; vector<ll> best(n, INF); vector<char> in(n); best[0] = 0; ll tot = 0;
    for (int it = 0; it < n; it++) {
        int u = -1; for (int v = 0; v < n; v++) if (!in[v] && (u < 0 || best[v] < best[u])) u = v;
        if (best[u] >= INF) return -1;                      // disconnected
        in[u] = 1; tot += best[u];
        for (int v = 0; v < n; v++) if (!in[v]) best[v] = min(best[v], w[u][v]);
    }
    return tot;
}
ll boruvka(int n, const vector<array<ll, 3>>& E) {         // {u, v, w}
    vector<int> d(n); iota(all(d), 0);
    auto f = [&](int x) { while (d[x] != x) x = d[x] = d[d[x]]; return x; };
    ll tot = 0; int comps = n;
    while (comps > 1) {
        vector<int> best(n, -1);
        for (int i = 0; i < sz(E); i++) {
            int a = f(E[i][0]), b = f(E[i][1]); if (a == b) continue;
            for (int c : {a, b}) if (best[c] < 0 || pair(E[i][2], i) < pair(E[best[c]][2], best[c])) best[c] = i;
        }
        bool any = false;
        for (int c = 0; c < n; c++) if (best[c] >= 0) {
            int i = best[c], a = f(E[i][0]), b = f(E[i][1]);
            if (a != b) d[a] = b, tot += E[i][2], comps--, any = true;
        }
        if (!any) break;                                    // disconnected: minimum spanning forest
    }
    return tot;
}

Borůvka on implicit graphs: each round, find every component’s cheapest outgoing edge with a problem-specific structure, $O(\log n)$ rounds:

• XOR-MST (weight $a_i\oplus a_j$): a binary trie of values not in the component; or divide and conquer on the trie: at each node with both children, connect them by the minimum XOR pair, $O(n\log n\log V)$ (Binary Trie).
• Manhattan MST: only $O(n)$ candidate edges (nearest point in each of 8 octants), then Kruskal (Manhattan).
• Euclidean MST: Delaunay edges only (Delaunay).
• Complete graph with weights $|a_i-a_j|$ or $f(\min )$…: sort and the candidate edges collapse to neighbours.
• 0/1 weights on a complete graph: components of the 0-graph via complement BFS (BFS).

Proof: Borůvka's rounds are safe and $O(\log n)$

With ties broken by edge index, all weights are effectively distinct, so the MST is unique. Each component’s cheapest outgoing edge is in it by the cut property, so adding all of them at once only adds MST edges, and they can’t form a cycle (a cycle would be in the unique MST). Every component merges with at least one other, so the number of components at least halves per round.

Classification and second-best

Which edges are in every / some / no MST (CF 160D): process weight classes in increasing order. An edge whose endpoints are already connected by lighter edges is in no MST. Among the remaining edges of the class, build a multigraph on the DSU components: an edge is in every MST iff it is a bridge of that multigraph, otherwise in some. Then union the class.

Proof: the every / some / none classification

Kruskal with any tie-breaking order produces exactly the MSTs, and before processing weight class $w$ the DSU components are the same for every tie-breaking (they are the components of the graph of edges lighter than $w$). An edge of class $w$ joining two vertices already connected by lighter edges is the strictly heaviest edge on a cycle, so it is in no MST. The remaining edges of the class, viewed on the component multigraph, are processed in arbitrary order and any spanning forest of that multigraph can be chosen; an edge is in every such spanning forest iff it is a bridge of the multigraph, and in some spanning forest otherwise.

Second-best (strictly heavier) MST: for every non-tree edge $(u,v,w)$, swap out the maximum tree edge on the $u$–$v$ path if it is lighter than $w$, else the largest edge strictly lighter than $w$; keep the best result. With binary lifting storing the two largest distinct values per jump, $O(m\log n)$.

ll secondBestMST(int n, const vector<array<ll, 3>>& E) {   // {w, u, v}; strictly larger than the MST, -1 if none
    vector<array<ll, 3>> T; ll W = kruskal(n, E, &T); if (sz(T) != n - 1) return -1;
    int LOG = 1; while ((1 << LOG) < n) LOG++;
    vector<vector<pair<int, ll>>> g(n); for (auto [w, u, v] : T) g[u].push_back({(int)v, w}), g[v].push_back({(int)u, w});
    using M2 = pair<ll, ll>;                                 // (max, max strictly below it), -1 = none
    auto mergeM = [](M2 a, M2 b) { ll m1 = max(a.first, b.first); ll m2 = max(a.first == m1 ? a.second : a.first, b.first == m1 ? b.second : b.first); return M2{m1, m2}; };
    vector<vector<int>> up(LOG, vector<int>(n)); vector<vector<M2>> mx(LOG, vector<M2>(n, {-1, -1})); vector<int> dep(n, -1), ord{0};
    dep[0] = 0; up[0][0] = 0;
    for (int i = 0; i < sz(ord); i++) for (auto [v, w] : g[ord[i]]) if (dep[v] < 0) dep[v] = dep[ord[i]] + 1, up[0][v] = ord[i], mx[0][v] = {w, -1}, ord.push_back(v);
    for (int k = 1; k < LOG; k++) for (int v = 0; v < n; v++) up[k][v] = up[k - 1][up[k - 1][v]], mx[k][v] = mergeM(mx[k - 1][v], mx[k - 1][up[k - 1][v]]);
    auto path = [&](int a, int b) {
        M2 r{-1, -1}; if (dep[a] < dep[b]) swap(a, b);
        for (int k = LOG - 1; k >= 0; k--) if (dep[a] - (1 << k) >= dep[b]) r = mergeM(r, mx[k][a]), a = up[k][a];
        if (a == b) return r;
        for (int k = LOG - 1; k >= 0; k--) if (up[k][a] != up[k][b]) r = mergeM(mergeM(r, mx[k][a]), mx[k][b]), a = up[k][a], b = up[k][b];
        return mergeM(mergeM(r, mx[0][a]), mx[0][b]);
    };
    set<array<ll, 3>> inT(all(T)); ll best = LLONG_MAX;
    for (auto& e : E) {
        if (inT.count(e) || e[1] == e[2]) { inT.erase(e); continue; }   // skip one copy of each tree edge
        auto [m1, m2] = path(e[1], e[2]);
        if (e[0] > m1) best = min(best, W + e[0] - m1);
        else if (m2 >= 0 && e[0] > m2) best = min(best, W + e[0] - m2);
    }
    return best == LLONG_MAX ? -1 : best;
}

Proof: a strictly second-best spanning tree is one swap away

Spanning trees are the bases of the graphic matroid, so for any two spanning trees $T,T^{\prime }$ there is a bijection $\sigma :T^{\prime }\setminus T\to T\setminus T^{\prime }$ with $T+e-\sigma (e)$ a spanning tree for every $e$ (Brualdi’s exchange lemma, Matroids). Let $T$ be an MST and $T^{\prime }$ a lightest tree with $w(T^{\prime })>w(T)$. Then $w(T^{\prime })-w(T)={\sum }_e(w(e)-w(\sigma (e)))$, and every term is $\ge 0$ because $T+e-\sigma (e)$ is a spanning tree and $T$ is minimum. Since the sum is positive, some term is positive, and it is at most the whole sum; the corresponding single swap $T+e-\sigma (e)$ has weight in $(w(T),w(T^{\prime })]$, so it is also optimal. For a fixed non-tree edge $e=(u,v)$, the best swap removes the heaviest path edge lighter than $w(e)$: the maximum $m_1$ if $m_1<w(e)$, otherwise ($m_1=w(e)$, by the cycle property it can’t exceed it) the largest value strictly below $m_1$.

Practical notes

• Edges already sorted, or weights are small integers: skip the $O(E\log E)$ sort and counting-sort the edges instead, giving Kruskal in $O(E\alpha (n))$.
• Borůvka parallelises naturally (every component’s cheapest edge is found independently each round) — the practical reason it’s the basis of every distributed/parallel MST algorithm.
• One edge forced in: contract it, then MST the rest. One edge forced out: delete it, then MST the rest.
• An edge’s weight decreases after the MST is built: add it; if it closes a cycle, remove the heaviest edge on that cycle (cycle property) — $O(n)$ per update, versus rebuilding or the full offline machinery below for many simultaneous changes.
• Single-linkage clustering: stopping Kruskal before $n-1$ edges (or removing the $k-1$ largest edges from a built MST) partitions the points into $k$ clusters — this is exactly single-linkage hierarchical clustering.
• Truly online insertions/deletions (not just weight changes known in advance): a link-cut tree maintains the MST incrementally; the divide-and-conquer method below is for the offline case where every update is known ahead of time.

Minimum diameter spanning tree

The shortest-path tree from the absolute center (the point, possibly inside an edge, minimising the farthest distance) has the minimum possible diameter, equal to twice the center’s eccentricity (Hassin–Tamir). Find the center with Floyd–Warshall and, for each edge, the upper envelope of $\min (d(u,x)+t,d(v,x)+w-t)$ (Kariv–Hakimi), in $O(n^3+mn\log n)$. Everything stays integral by doubling.

struct MDST { ll diameter; int vertex = -1, edge = -1; ll off2 = 0; vector<int> tree; };
MDST minDiameterTree(int n, const vector<array<ll, 3>>& E) {   // {u, v, w}, connected, w >= 0
    const ll INF = LLONG_MAX / 4; vector<vector<ll>> d(n, vector<ll>(n, INF));
    for (int i = 0; i < n; i++) d[i][i] = 0;
    for (auto [u, v, w] : E) d[u][v] = min(d[u][v], w), d[v][u] = min(d[v][u], w);
    for (int k = 0; k < n; k++) for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
    MDST b; b.diameter = INF;
    for (int v = 0; v < n; v++) { ll e = *max_element(all(d[v])); if (2 * e < b.diameter) b.diameter = 2 * e, b.vertex = v; }
    vector<int> ord(n);
    for (int e = 0; e < sz(E); e++) {
        auto [u, v, w] = E[e]; iota(all(ord), 0);
        sort(all(ord), [&](int a, int c) { return d[u][a] > d[u][c]; });
        int p = ord[0];
        for (int i = 1; i < n; i++) {
            int x = ord[i];
            if (d[v][x] > d[v][p]) {
                ll cand = d[u][x] + d[v][p] + w;
                if (cand < b.diameter) b.diameter = cand, b.vertex = -1, b.edge = e, b.off2 = d[v][p] + w - d[u][x];
                p = x;
            }
        }
    }
    vector<vector<pair<int, int>>> g(n); for (int e = 0; e < sz(E); e++) g[E[e][0]].push_back({(int)E[e][1], e}), g[E[e][1]].push_back({(int)E[e][0], e});
    vector<ll> dist(n, INF); vector<int> pe(n, -1); priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<>> pq;
    if (b.vertex >= 0) dist[b.vertex] = 0; else dist[E[b.edge][0]] = b.off2, dist[E[b.edge][1]] = 2 * E[b.edge][2] - b.off2;
    for (int v = 0; v < n; v++) if (dist[v] < INF) pq.push({dist[v], v});
    while (sz(pq)) {
        auto [du, u] = pq.top(); pq.pop(); if (du != dist[u]) continue;
        for (auto [v, e] : g[u]) if (du + 2 * E[e][2] < dist[v]) dist[v] = du + 2 * E[e][2], pe[v] = e, pq.push({dist[v], v});
    }
    int roots = 0; for (int v = 0; v < n; v++) if (pe[v] >= 0) b.tree.push_back(pe[v]); else roots++;
    if (roots == 2) b.tree.push_back(b.edge);
    return b;
}

Proof sketch: the absolute center gives the optimum

Any spanning tree $T$ has a center point $c_T$ (midpoint of its diameter path) with tree eccentricity $\text{diam}(T)/2$; graph distances are at most tree distances, so the graph eccentricity of $c_T$ is $\le \text{diam}(T)/2$, hence $\text{diam}(T)\ge 2\text{ecc}(c^{\ast })$ for the absolute center $c^{\ast }$. Conversely the shortest-path tree from $c^{\ast }$ has every vertex within $\text{ecc}(c^{\ast })$ of the root, so its diameter is $\le 2\text{ecc}(c^{\ast })$. On an edge $(u,v)$ at position $t$, the distance to $x$ is $\min (d(u,x)+t,d(v,x)+w-t)$, and the eccentricity’s local minima occur where an increasing line of one vertex meets the decreasing line of another with larger $d(v,\cdot )$: scanning $x$ by decreasing $d(u,x)$ and keeping the vertex with the largest $d(v,\cdot )$ so far enumerates those breakpoints, each with value $(d(u,x)+d(v,p)+w)/2$.

Dynamic MST (offline weight changes)

MST weight after each of $q$ updates “set the weight of edge $i$ to $x$”: divide and conquer on the query interval with contraction (edges in every MST when the interval’s edges are forced in) and reduction (edges in no MST when the interval’s edges are forced out); each level keeps only $O(\text{interval length})$ edges. $O((m+q){\log }^2)$, rollback DSU.

vector<ll> dynamicMST(int n, const vector<array<ll, 3>>& EIn, const vector<pair<int, ll>>& qs) {   // {u, v, w}
    int m = sz(EIn), q = sz(qs); if (!q) return {};
    vector<int> st(m), ed(m), chk(m), pa(n), rk(n); vector<ll> cost(m);
    for (int i = 0; i < m; i++) st[i] = EIn[i][0], ed[i] = EIn[i][1], cost[i] = EIn[i][2];
    iota(all(pa), 0);
    auto find = [&](int x) { while (pa[x] != x) x = pa[x]; return x; };
    auto unite = [&](int p, int r, vector<pair<int, int>>& sn) {
        p = find(p), r = find(r); if (p == r) return false;
        if (rk[p] < rk[r]) swap(p, r);
        sn.push_back({r, pa[r]}); pa[r] = p;
        if (rk[p] == rk[r]) sn.push_back({p, -1}), rk[p]++;
        return true;
    };
    auto revert = [&](vector<pair<int, int>>& sn) { for (int i = sz(sn) - 1; i >= 0; i--) { auto [x, y] = sn[i]; if (y < 0) rk[x]--; else pa[x] = y; } sn.clear(); };
    auto cmp = [&](int a, int b) { return pair(cost[a], a) < pair(cost[b], b); };
    auto contract = [&](int s, int e, vector<int> v, vector<int>& must, vector<int>& maybe) {
        sort(all(v), cmp); vector<pair<int, int>> sn;
        for (int i = s; i <= e; i++) unite(st[qs[i].first], ed[qs[i].first], sn);
        for (int i : v) if (unite(st[i], ed[i], sn)) must.push_back(i);
        revert(sn);
        for (int i : must) unite(st[i], ed[i], sn);
        for (int i : v) if (unite(st[i], ed[i], sn)) maybe.push_back(i);
        revert(sn);
    };
    vector<ll> ans(q);
    for (int i = 0; i < q; i++) chk[qs[i].first]++;
    auto solve = [&](auto&& self, int s, int e, vector<int> v, ll cv) -> void {
        if (s == e) {
            cost[qs[s].first] = qs[s].second;
            if (st[qs[s].first] == ed[qs[s].first]) { ans[s] = cv; return; }
            ll mn = qs[s].second; for (int i : v) mn = min(mn, cost[i]);
            ans[s] = mn + cv; return;
        }
        int mid = (s + e) / 2; vector<int> lv = v, rv = v, must, maybe;
        for (int i = mid + 1; i <= e; i++) if (--chk[qs[i].first] == 0) lv.push_back(qs[i].first);
        vector<pair<int, int>> sn;
        contract(s, mid, lv, must, maybe);
        ll lcv = cv; for (int i : must) lcv += cost[i], unite(st[i], ed[i], sn);
        self(self, s, mid, maybe, lcv); revert(sn);
        must.clear(), maybe.clear();
        for (int i = mid + 1; i <= e; i++) chk[qs[i].first]++;
        for (int i = s; i <= mid; i++) if (--chk[qs[i].first] == 0) rv.push_back(qs[i].first);
        ll rcv = cv; contract(mid + 1, e, rv, must, maybe);
        for (int i : must) rcv += cost[i], unite(st[i], ed[i], sn);
        self(self, mid + 1, e, maybe, rcv); revert(sn);
        for (int i = s; i <= mid; i++) chk[qs[i].first]++;
    };
    vector<int> init; for (int i = 0; i < m; i++) if (!chk[i]) init.push_back(i);
    solve(solve, 0, q - 1, init, 0);
    return ans;
}

Proof sketch: contraction and reduction

Within a query interval, only the edges updated in it (the “dynamic” set $D$) can change weight. Contraction: if a static edge is chosen by Kruskal even when all of $D$ are added first (with weight $-\infty$), it belongs to every MST arising in the interval (cut property: it is the lightest edge across a cut no matter how $D$‘s weights are set), so it can be contracted and its weight added to the answer. Reduction: if a static edge is not chosen by Kruskal when all of $D$ are removed (weight $+\infty$), it closes a cycle of lighter static edges, so it is in no MST in the interval (cycle property) and can be dropped. After both steps at most $|D|$ vertices’ worth of structure remains, so the number of static edges kept is $O(|D|)$; recursion halves $D$, giving $O(\log q)$ levels each with near-linear Kruskal work.

Related

• Counting spanning trees and MSTs: Kirchhoff’s theorem per weight class (Matrix-Tree).
• Directed MST (arborescence): Chu–Liu/Edmonds, not Kruskal (Directed MST).
• Kruskal reconstruction tree for “maximum edge on the path / reachable with edges $\le x$” queries (KRT).
• Spanning tree with exactly $k$ special edges: Aliens trick on Kruskal (Aliens).
• Degree-constrained MST, Steiner tree: NP-hard in general (Steiner Tree).