Skip to content

最小生成树

我们定义无向连通图的 最小生成树（Minimum Spanning Tree，MST）为边权和最小的生成树。

注意：只有连通图才有生成树，而对于非连通图，只存在生成森林。

Kruskal算法

Kruskal是一个贪心算法，我们从最小边权的边开始，按边权从小到大依次加入，如果某次加边产生了环，就扔掉这条边，直到加入了\(n-1\)条边，即得到了最小生成树。

动画演示

正确性证明使用归纳法(proof by induction)。证明任何时候算法选择的边集都被某棵 MST 所包含。

基础：对于算法刚开始时，显然成立（最小生成树存在）。

归纳：假设某时刻成立，当前边集为 \(F\)，令 \(T\) 为这棵 MST，考虑下一条加入的边 \(e\)。

如果 \(e\) 属于 \(T\)，那么成立。

否则，\(T+e\) 一定存在一个环，考虑这个环上不属于 \(F\) 的另一条边 \(f\)（一定只有一条）。

首先，\(f\) 的权值一定不会比 \(e\) 小，不然 \(f\) 会在 \(e\) 之前被选取。

然后，\(f\) 的权值一定不会比 \(e\) 大，不然 \(T+e-f\) 就是一棵比 \(T\) 还优的生成树了。

所以，\(T+e-f\) 包含了 \(F\)，并且也是一棵最小生成树，归纳成立。

实现（使用并查集）： 

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

//Kruskal最小生成树模板题
int n, m, father[100000];

struct node{
    int src, dst;
    int val;
};

bool cmp(node a, node b){return a.val < b.val;}

int findFather(int a){
    int t = a;
    while(a != father[a])a = father[a]; //找到根节点
    return a;
}

void init(){
    for(int i = 1; i <= n; i++)father[i] = i;
}

int unionSet(int x, int y){ //和并查集一样，如果将根合并
    int fx = findFather(x);
    int fy = findFather(y);
    if(fx != fy){
        father[fx] = fy;
        return  1;
    }return 0;
}

int main(){
    while(cin>>n){
        if(n == 0)break;
        init(); //初始化不能丢
        cin>>m;
        int ans = 0;
        vector<node> pool(m);
        for(int i = 0; i < m; i++){
            cin>>pool[i].src>>pool[i].dst>>pool[i].val;
        }

        sort(pool.begin(), pool.end(), cmp);
        int k = 0, i = 0;
        while(k < n - 1){ 
            if(unionSet(pool[i].src, pool[i].dst)){ //如果两个节点的根不一样则合并，本质上将两个预给定的边选择出来
                //也不会成环
                k++;
                ans += pool[i].val;
            }
            i++;
        }
        cout<<ans<<endl;
    }
    return 0;
}

习题

次小生成树和严格次小生成树

见OI-Wiki