『学习笔记』- 图论-最小生成树-Kruskal
xzy_AK_IOI
·
·
算法·理论
最小生成树是指在一个连通图中找出边权和最小的一棵树且此树可以将所有点联通。
下图为一个无向有权且联通的图：
则此图的最小生成树如下图所示
容易看出，最小生成树满足以下几个性质：
- 设图中点数为n，则最小生成树边数为n-1。
- 最小生成树中无环路。
其步骤为：
1. 将边以边权从小到大排序。
2. 依次遍历每条边，若将此边插入未产生环路则将其加入最小生成树中。
判断环路可以使用[并查集](https://baike.baidu.com/item/%E5%B9%B6%E6%9F%A5%E9%9B%86/9388442?fr=ge_ala)。
并查集操作如下：
### 查询
如图，这是一棵树
我们用集合$s$来记录每个节点的父节点，则$s$集合为
|节点编号|0|1|2|3|4|5|
|:-:|:-:|:-:|:-:|:-:|:-:|:-:|
|父节点|0|0|1|2|2|0|
**注意，将无父节点的父节点编号设为其自己。**
如果我们想查找某节点的根（如节点$4$）的根，则可以一直递归直到节点编号等于其父节点编号。
代码实现如下：
```cpp
int find_set(int x){
if (s[x]==x) return s[x];
else return find_set(s[x]);
}
```
但这样有个弊端，就是每次查找节点$4$的根时，都要查找多次，但如果这棵树变成这样：
就方便很多。
为了将树变成如上图所示，我们可以使用路径压缩来优化并查集，即在递归时顺便把父节点变为根节点，代码如下文所示：
```cpp
int find_set(int x){
if (s[x]!=x){
s[x]=find_set(s[x]);
}
return s[x];
}
```
### 合并
若我们想将下图中的$4$与$8$节点合并，
则只需将$0$与$5$节点合并即可，合并代码如下：
```cpp
int e1=find_set(a);
int e2=find_set(b);
s[e1]=e2;
```
判断环路只需判断两个点的根节点是否相等即可。
- 若相等，则再添加一条边则会形成环路。
- 反之不会。
下面分析时间复杂度（设图有$m$条边，$n$个点）：
- 排序复杂度为$O(m\ log_2\ m)$。
- 并查集复杂度为$O(n)$。
- 遍历边复杂度为$O(m)$。
总时间复杂度为$O(m\ log_2\ m)$。
模板代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
const int M=2e5+10;
struct edge{
int from;
int to;
int w;
};
edge e[M];
int cnt=0;
int n,m;
int s[5010];
bool cmp(edge a,edge b){
return a.w<b.w;
}
int find_set(int x){
if (x!=s[x]){
s[x]=find_set(s[x]);
}
return s[x];//路径压缩
}
void Kruskal(){
sort(e+1,e+1+m,cmp);
for (int i=1;i<=n;i++){
s[i]=i;//并查集初始化
}
int ans=0,sum=0;
for (int i=1;i<=m;i++){
if (sum==n-1){//小优化，边数为点数少一时退出循环
break;
}
int set1=find_set(e[i].from);
int set2=find_set(e[i].to);
if (set1==set2){
continue;//判断环路
}
ans+=e[i].w;
sum++;
s[set1]=set2;//合并
}
if (sum==n-1){
cout<<ans;
}
else{
cout<<"orz";
}
}
```
### 练习题目
- [P3366 【模板】最小生成树](https://www.luogu.com.cn/problem/P3366)
- [P2330 [SCOI2005] 繁忙的都市](https://www.luogu.com.cn/problem/P2330)
- [P8074 [COCI2009-2010#7] SVEMIR](https://www.luogu.com.cn/problem/P8074)