算法心传·最小生成树 – 将去未还的随笔

什么是最小生成树呢？
在一个无向连通图中，如果存在一个子图包含原图的所有顶点，且是一棵树（即无环且连通），那么这棵树称为原图的生成树。
最小生成树（Minimum Spanning Tree, MST）是所有生成树中边权和最小的那一棵。
值得注意的是若图不连通，则不存在生成树，但可以求出每个连通分量的最小生成森林。

一、最小生成树

关于最小生成树这里不再赘述，直接展开讲解性质和模板。

1. 切割性质：

定义：将顶点集 $V$ V 划分为两个非空子集 $S$ S 和 $V ∖ S$ V∖S，横跨两个集合的所有边称为一个切割。
性质：在最小生成树中，权重最小的横跨边一定属于某棵最小生成树。

2. 回路性质

定义：图中的一个简单环。
性质：环上权重最大的边一定不会出现在任何最小生成树中。

这两个性质是贪心算法（Prim、Kruskal）正确性的理论基础。
关于贪心算法，我们可以理解为通过不断的选择局部最优，再到最后选择时，我们得到的就是全局最优，大家可以自行查阅理解学习，尤其是关于贪心和DP的区别方面要能理解分清。

二、经典算法

1. Kruskal 算法（克鲁斯卡尔）

思路：将所有边按权值从小到大排序，依次尝试加入，如果加入后不形成环（即边的两个端点当前不在同一连通块），则加入该边。
正确性：基于切割性质——每次选择当前最小的且能连接两个不同连通块的边，一定是某个切割的最小边。
时间复杂度：

排序 $O (m \log m)$ O(mlogm)
并查集操作 $O (m α (n))$ O(mα(n))
总体 $O (m \log m)$ O(mlogm)，适合稀疏图。

模板代码：

struct DSU {
    vector<int> parent, rank_; // rank_ 记录树的高度（秩）

    DSU(int n) {
        parent.resize(n + 1);
        rank_.resize(n + 1, 0);
        for (int i = 1; i <= n; ++i)
            parent[i] = i;
    }

    int find(int x) {
        if (parent[x] != x)
            parent[x] = find(parent[x]); // 路径压缩
        return parent[x];
    }

    void unite(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX == rootY)
            return;

        // 按秩合并：将秩小的树合并到秩大的树
        if (rank_[rootX] < rank_[rootY]) {
            parent[rootX] = rootY;
        } else if (rank_[rootX] > rank_[rootY]) {
            parent[rootY] = rootX;
        } else {
            parent[rootY] = rootX;
            rank_[rootX]++;
        }
    }

    bool same(int x, int y) {
        return find(x) == find(y);
    }
};
// ----------------------------------

struct Edge {
    int u, v, w;
    bool operator<(const Edge& other) const {
        return w < other.w; // 按边权升序排序
    }
};

/**
 * Kruskal 算法求最小生成树
 * @param n 顶点个数（编号从 1 到 n）
 * @param edges 边列表
 * @return 最小生成树的权值和，若图不连通则返回 -1
 */
int kruskal(int n, const vector<Edge>& edges) {
    // 复制边并排序（也可直接对原边排序，但传入 const 引用，需复制一份）
    vector<Edge> sortedEdges = edges;
    sort(sortedEdges.begin(), sortedEdges.end());

    DSU dsu(n);              // 初始化并查集
    int mst_weight = 0;      // 总权值
    int cnt = 0;             // 已选边数

    for (const auto& e : sortedEdges) {
        if (!dsu.same(e.u, e.v)) { // 两点不在同一连通块
            dsu.unite(e.u, e.v);
            mst_weight += e.w;
            cnt++;
            if (cnt == n - 1) break; // 生成树已形成
        }
    }

    return (cnt == n - 1) ? mst_weight : -1;
}

2. Prim 算法（普里姆）

思路：从任意一个顶点开始，维护一个已选点集，每次选择连接已选点集和未选点集的最短边，将对应新点加入集合并累加权值。
朴素实现：用数组维护每个点到已选点集的最短距离，每次 $O (n)$ O(n) 扫描，总 $O (n^{2})$ O(n2)，适合稠密图。
堆优化：使用优先队列维护候选边，每次取出最小边，如果连接的点未访问则加入。复杂度 $O (m \log m)$ O(mlogm)，适合稀疏图。
模板代码（堆优化版）：

typedef pair<int, int> pii; // (dist, vertex)

int prim(int n, vector<vector<pii>>& g) {
    vector<bool> vis(n, false);
    priority_queue<pii, vector<pii>, greater<pii>> pq;
    pq.push({0, 0}); // 从顶点 0 开始
    int mst_weight = 0, cnt = 0;
    while (!pq.empty() && cnt < n) {
        auto [d, u] = pq.top(); pq.pop();
        if (vis[u]) continue;
        vis[u] = true;
        mst_weight += d;
        cnt++;
        for (auto& [v, w] : g[u]) {
            if (!vis[v]) {
                pq.push({w, v});
            }
        }
    }
    return cnt == n ? mst_weight : -1;
}

注意：以上 Prim 堆优化版本可能重复入队，但每个顶点只会被处理一次。在稠密图中，朴素 $O (n^{2})$ O(n2) 的 Prim 可能比堆优化更快，因为 $m$ m 接近 $n^{2}$ n2 时 $m \log m > n^{2}$ mlogm>n2。

二、经典例题

P3366 【模板】最小生成树 – 洛谷

次小生成树：

严格次小：权值严格大于最小生成树。
非严格次小：权值可以等于最小生成树。
常用方法：先求 MST，再枚举非树边，替换树上路径的最大边（或严格次大边），取最小值。

最小生成树唯一性：

若任意切割中最小边唯一，则 MST 唯一。
可以通过检查边权相等的边是否可以在不同 MST 中被替换来判断。