Kruskal学习笔记

Kruskal 学习笔记

最小生成树

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

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

Kruskal 算法

介绍

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

证明

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

证明:使用归纳法,证明任何时候 K 算法选择的边集都被某棵 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$ ,并且也是一棵最小生成树,归纳成立。

(引用自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;
}
感谢支持,您的支持将是我原创的动力!