文章目录
Kruskal算法简介
K
r
u
s
k
a
l
Kruskal
Kruskal 是基于贪心算法的
M
S
T
MST
MST 算法，核心思想为以边为中心查找最小生成树，时间复杂度为
O
(
m
l
o
g
2
m
)
O(mlog_{2}m)
O(mlog2m)，其中的
m
m
m 为边数
具体算法可分为两个步骤：
1.以边权为优先级来进行排序
2.使用并查集查找连通性，如果不连通，则加边，加答案
Kruskal算法前置知识
1.对于 v e c t o r vector vector 的容器排序算法（使用 s o r t sort sort 即可）
sort(T.begin(),T.end(),cmp);//这是vector的排序方法
解释： T . b e g i n ( ) T.begin() T.begin() 是 v e c t o r vector vector 的起始部分， T . e n d ( ) T.end() T.end() 是 v e c t o r vector vector 的结束部分， T T T 是 v e c t o r vector vector 的容器名
sort 中的cmp函数
c
m
p
cmp
cmp 为
s
o
r
t
sort
sort 重构函数，需要自己定义，这个函数的类型为
b
o
o
l
bool
bool ，内部变量的类型便是需要排序的容器的类型
cmp模版code如下↓
T name;
bool cmp(T x,T y){return x op y}
sort(name(first),name(last),cmp)
T
T
T 为容器类型，
n
a
m
e
name
name 为容器名字，
n
a
m
e
(
f
i
r
s
t
)
name(first)
name(first) 代表容器的第一位，
n
a
m
e
(
l
a
s
t
)
name(last)
name(last) 表示容器的最后一位
2.使用结构体的构造来赋值
Edge(int a,int b,int c):u(a),v(b),w(c){};
上述构造函数的代码的意思等同于↓：
Edge(int a,int b,int c){u=a,v=b,w=c;}
在结构体里加边的操作也就为：T.push_back(Edge(u,v,w));
3.容器 v e c t o r vector vector 的定义
我们需要用容器来管理结构体
也就是将结构体给定义在容器里
vector<Node> T;//其中T为容器名,Node为结构体名
定义code总结↓：
struct Node{
int u,v,w;//定义类型
Edge(int a,int b,int c):u(a),v(b),w(c){};//使用构造
};
bool (Node x,Node y){return x.w<y.w}//具体使用vector里的哪一个定义排序的函数
vector<Node> T;//使用容器来管理结构体
sort(T.begin(),T.end(),cmp)//其中T为容器名
算法思考
我们先给出一个题目来进行思考↓：
x x x 市共有 n n n 个岛屿， m m m 种修桥的方案由于 x x x 市的市长是一个黑心市长，所以他想要选择一种方案使得总共修桥的钱最少
每年他可以修一座桥，问：需要几年才能使得所有的岛屿之间都可以互相同行，最少修桥的钱为多少？
我们可以知道：修桥的钱数就是边权，岛屿的名字就是点的编号
第一个问题很好解答，使得所有点之间都可以连通的最少边数为
N
−
1
N-1
N−1 条边
第二个问题我们就需要进行
K
r
u
s
k
a
l
Kruskal
Kruskal 进行求最小生成树了
输入格式为
第 1 1 1 行，两个整数 n n n , m m m
第 2 2 2 ~ n + 1 n+1 n+1 行，每行三个整数 u u u , v v v , w w w ，表示所连接的两点及其边权
我们先给出一组样例↓
4 6
1 2 11
2 3 13
3 4 9
4 1 21
1 3 23
4 2 20
样例解释如图示↓
样例详细示范与解释
因为我们是需要" 花最少的钱，办最多的事 "，所以我们需要先以边的权值为优先级进行排序，结果为↓
3 4 9
1 2 11
2 3 13
4 2 20
4 1 21
1 3 23
那么我们就可以开始进行判断了，每一次重复的过程为：查找两个点是否连通，如果不连通，则加边
int x=find(wei[i].u),y=find(wei[i].v);//查找两个点的祖先
if(x!=y){//如果祖先相同，则他们连通，在同一个集合内
f[x]=y;//将两条边连在一起
ans+=wei[i].w;//将它的权值加在最终答案里
cnt++;//已经连接的边数+1
}
解释：因为我们最开始已经排过序了，所以如果不连通，那么这条边一定是连接这两个点的最小代价
最后，如果两个点不连通，直接加边和答案，如果边数已经满足最少边数为
N
−
1
N-1
N−1 条，则返回答案
return cnt==n-1?ans:-1;//如果边数是n-1条则返回答案，否则没有答案，无法连接所有边
如何使用并查集查找两个点的连通性，可见我的另一篇博文：并查集【模版】& 路径压缩优化
动图视频如下：
<iframe allowfullscreen="true" data-mediaembed="csdn" frameborder="0" id="vK0qYnrm-1711261544794" src="https://live.csdn.net/v/embed/373319"></iframe>kruskal模版code↓
int kruskal(int n,int m,vector<Edge> &wei){
sort(wei.begin(),wei.end(),cmp);
int ans=0,cnt=0;
for(int i=0;i<m;i++){
int x=find(wei[i].u),y=find(wei[i].v);
if(x!=y){
f[x]=y;
ans+=wei[i].w;
cnt++;
}
}
return cnt==n-1?ans:-1;
}
例题：洛谷P3366 【模板】最小生成树code↓
#include <bits/stdc++.h>
using namespace std;
const int maxn=2e5+7;
struct Edge{
int u,v,w;
Edge(int a,int b,int c):u(a),v(b),w(c){};
};
int f[maxn]={},n,m;
bool cmp(Edge x,Edge y){
return x.w<y.w;
}
int find(int x){return f[x]==x?x:f[x]=find(f[x]);}
vector<Edge> wei;
int kruskal(int n,int m,vector<Edge> &wei){
sort(wei.begin(),wei.end(),cmp);
int ans=0,cnt=0;
for(int i=0;i<m;i++){
int x=find(wei[i].u),y=find(wei[i].v);
if(x!=y){
f[x]=y;
ans+=wei[i].w;
cnt++;
}
}
return cnt==n-1?ans:-1;
}
int init(){
for(int i=1;i<=n;i++) f[i]=i;
return 0;
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++) f[i]=i;
for(int i=1;i<=m;i++){
int u,v,w;
cin>>u>>v>>w;
wei.push_back(Edge(u,v,w));//因为是无向图，所以需要反过来再加一次边
wei.push_back(Edge(v,u,w));
}
int ans=kruskal(n,2*m,wei);//因为是无向图，所以边数是原边数的两倍
if(ans==-1) cout<<"orz";
else cout<<ans;
return 0;
}
这么一点代码当然是可以 A C AC AC 的
