最小生成树 (Minimum Spanning Tree)¶

在一个连通无向加权图中，最小生成树（MST）是包含图中所有顶点的极小连通子图，且边的权值之和最小。常见算法有 Kruskal 和 Prim。

Kruskal 算法 (稀疏图首选)¶

基于贪心思想与并查集。按边权升序排序所有边，依次尝试加入生成树，若当前边两端点已在同一连通分量中则跳过。

时间复杂度：\(\mathcal{O}(E \log E)\)，空间复杂度：\(\mathcal{O}(V + E)\)。

#include <vector>
#include <algorithm>
#include <numeric>

struct Edge {
    int u, v;
    long long weight;
    bool operator<(const Edge &other) const {
        return weight < other.weight;
    }
};

struct DSU {
    std::vector<int> parent;
    DSU(int n) : parent(n + 1) {
        std::iota(parent.begin(), parent.end(), 0);
    }
    int find(int i) {
        if (parent[i] == i) return i;
        return parent[i] = find(parent[i]);
    }
    bool unite(int i, int j) {
        int root_i = find(i), root_j = find(j);
        if (root_i == root_j) return false;
        parent[root_i] = root_j;
        return true;
    }
};

// 返回 {MST 总权值, 选中的边数}
// 若选中的边数 < n - 1，说明图不连通
std::pair<long long, int> kruskal(int n, std::vector<Edge> &edges) {
    std::sort(edges.begin(), edges.end());
    DSU dsu(n);

    long long total_weight = 0;
    int edge_count = 0;

    for (const auto &e : edges) {
        if (dsu.unite(e.u, e.v)) {
            total_weight += e.weight;
            edge_count++;
            if (edge_count == n - 1) break;
        }
    }
    return {total_weight, edge_count};
}

堆优化 Prim 算法 (稠密图适用)¶

从任意起点出发，维护已知生成树集合到树外顶点的最短距离，类似 Dijkstra 算法。

时间复杂度：\(\mathcal{O}((V + E) \log V)\)。

#include <vector>
#include <queue>

struct AdjEdge {
    int to;
    long long weight;
};

std::pair<long long, int> prim(int n, const std::vector<std::vector<AdjEdge>> &adj) {
    std::vector<bool> vis(n + 1, false);
    std::priority_queue<std::pair<long long, int>, 
                        std::vector<std::pair<long long, int>>, 
                        std::greater<std::pair<long long, int>>> pq;

    // 从 1 号顶点开始
    pq.push({0, 1});
    long long total_weight = 0;
    int count = 0;

    while (!pq.empty()) {
        auto [w, u] = pq.top();
        pq.pop();

        if (vis[u]) continue;
        vis[u] = true;
        total_weight += w;
        count++;

        for (const auto &e : adj[u]) {
            if (!vis[e.to]) {
                pq.push({e.weight, e.to});
            }
        }
    }
    return {total_weight, count};
}

LeetCode 经典真题精选与题解提示¶

LeetCode 1584 - 连接所有点的最小费用 (Min Cost to Connect All Points) 中等
提示

稠密图 MST 经典应用。
- 平面上 \(n\) 个点两两之间均存在曼哈顿距离边，为完全图（边数 \(\mathcal{O}(n^2)\)）。
- 既可以使用 Kruskal 算法（排序所有边 \(\mathcal{O}(n^2 \log n)\) 结合并查集），也可以使用无需堆优化的朴素 Prim 算法在 \(\mathcal{O}(n^2)\) 时间内求解，后者在稠密图上常数更小、速度更快。
LeetCode 1168 - 水资源分配优化 (Optimize Water Distribution in a Village) 困难
提示

超级虚拟源点建图。
- 允许在村庄内打井（点权），也允许在两村庄间铺设水管（边权）。
- 引入虚拟源点 0（地下总水源），从 0 向每个村庄 \(i\) 连一条权为打井花费 \(wells[i-1]\) 的边。
- 打井操作由此等价为“连接到超级水源 0”。在包含 \(n+1\) 个顶点的扩展图上运行 Kruskal 算法求 MST 权值总和即可。
LeetCode 1489 - 找到最小生成树里的关键边和伪关键边 (Find Critical and Pseudo-Critical Edges in Minimum Spanning Tree) 困难
提示

MST 唯一定理与边存在性判定。
- 首先运行一次 Kruskal 计算全图的基准 MST 最小权值 \(val\)。
- 枚举每条边 \(e\)：
  1. 判断是否为关键边：在边集中强制剔除边 \(e\)，重新计算 MST。若新图不连通或新的生成树权值 \(> val\)，说明没有边 \(e\) 无法取得最优解，\(e\) 为关键边；
  2. 判断是否为伪关键边：若不是关键边，但在计算 MST 时强制先加入边 \(e\)（将 \(e\) 的两个端点先合并并把边权计入），之后继续运行 Kruskal。若求得的生成树权值仍恰好等于 \(val\)，则 \(e\) 为伪关键边。