Kruskal 学习笔记

最小生成树

在无向图中，连通且无环的图称为树(Tree)。给定无向图G=(V,E)G=(V,E)，连接GG中所有点，且边集是EE的子集的树称为GG的生成树(Spanning Tree)，而权值最小的生成树称为最小生成树(Minimal Spanning Tree , MST)。s

例题:Luogu P3366 【模板】最小生成树

Kruskal 算法

###介绍

Kruskal算法由Kruskal发明，用于构造MST，它易于编写，而且效率很高。该算法的基本思想是从大到小加入边，是个贪心算法。

证明

思路很简单，为了造出一棵最小生成树，我们从最小边权的边开始，按边权从小到大依次加入，如果某次加边产生了环，就扔掉这条边，直到加入了 n−1n-1 条边，即形成了一棵树。

证明：使用归纳法，证明任何时候 K 算法选择的边集都被某棵 MST 所包含。

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

归纳：假设某时刻成立，当前边集为 FF ，令 TT 为这棵 MST，考虑下一条加入的边 ee 。

如果 ee 属于 TT ，那么成立。

否则，T+eT+e 一定存在一个环，考虑这个环上不属于FF 的另一条边 ff（一定只有一条）。

首先，ff 的权值一定不会比 ee小，不然 ff 会在 ee 之前被选取。

然后，ff 的权值一定不会比 ee 大，不然 T+e−fT+e-f 就是一棵比 TT 还优的生成树了。

所以，T+e−fT+e-f 包含了 FF ，并且也是一棵最小生成树，归纳成立。

（引用自OI-Wiki)

实现

因为需要查询两点是否连通，所以我们这里可以使用并查集进行维护。

算法总共会经历三个流程：

1.读入后，按照从小到大的顺序将边排序

2.遍历排序后的边的数组，如果当前边的左右顶点未连通（两点未在同一集合中），则加入这条边（将两点所在集合合并）；如果已经连通，则跳过这条边来考虑下一跳边。

3.若加入的边数等于点数减一，则认为已经形成了一棵MST，跳出循环。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
const int MAXN = 5010;     //点数范围
const int MAXM = 200010;   //边数范围
struct Node {int u, v, w;}E[MAXM]; //结构体存边，u、v为边所连接的两点，w为边权
int cnt = 0;
int cmp(Node i, Node j) {return i.w < j.w;} //自定义排序方法
int find(int x){return p[x] == x ? x : p[x] = find(p[x]);} //并查集寻根函数
inline int Kruskal(){
    int ans = 0;
    for(int i = 0;i < n;i++) p[i] = i; //初始化并查集
    sort(E, E + M, cmp); //将边按照边权大小排序
    for(int i = 0;i < m;i++) {
      	int x = find(E[i].u); 
      	int y = find(E[i].v)；
  	    if(x != y){         //如果两个点没有连通
            cnt++;        //已经加入的边数加一
            ans += E[i].w;  //存入这条边的权值
            p[x] = y;     //加入这条边，并使两点连通
        }
      if(cnt == n - 1) break; //若边数等于点数-1，则已经形成MST，跳出循环
    }
    return ans;
}