最小生成树是数据结构中一个经典的问题,一次在刷题的过程中遇到了这类的问题,那时候遇到这类问题就很迷茫。建立最小生成树有两种方法,一种是以点建树,每次都选择最近的点,即prim
算法;另一种是以边建树,每次都选择最短的边,即kruskal
算法,prim
算法可以不借助并查集就可建树,但是当我们用kruskal
算法是就需要用到并查集了。
# 并查集的的作用
并查集的作用是判断两个顶点之间是否是连通状态。
# 并查集的思想
初始有N个各不相同的集合,输入其中的一些边,使其中的顶点相互连通,直至所有的顶点都相互连通,成为一个集合,若他们的权值之和最小,则说明这是一颗最小生成树。 还是用通俗的语言来说吧。亲戚关系,现在有三个原本互相不认识的人聚到了一起,他们分别是A,B,C;随着三人之间的更加熟悉,A和B是亲戚关系(即A和B之间是连通的,他们合并到一个集合),B和C之间也是亲戚关系,所以A和C之间也是亲戚,所以A、B、C都是亲戚关系,即他们都是连通的(三者是同一个集合),这个时候我们怎么知道他们三个是亲戚关系?只需要从他们之中找出一个代表,A二大爷和B大表叔是同一个人X,这个时候两个人就以X为枢纽建立了亲戚关系,为了方便,每次把最后一个并入到集合中的人,当做枢纽X。
# 并查集的代码
#include<iostream>
using namespace std;
const int Max=1e5+2;//假设结点的最大数目不超过Max
int fa[Max];
void build(int n)//初始化,n个人都在不同的集合
{
for(int i=1;i<=n;i++){
fa[i]=i;
}
return ;
}
int Find(int m)//这个函数作用是寻找他们枢纽X,一定要用int
{
return fa[m]==m?m:fa[m]=Find(fa[m]);
}
bool che(int x,int y)//判断两个点是否属于同一个集合,即亲戚关系
{
return Find(x)==Find(y);
}
void mer(int x,int y)//如果不是亲戚关系就把他们合并到一起
{
if(!che(x,y)){
fa[fa[x]]=fa[y];
}
return ;
}
int main()
{
int n;
cin >> n;
build(n);
int p;//假设要输入p条边
cin >> p;
while(p--){
int x,y;
cin >> x >> y;
mer(x,y);
}
int q;//检查两个点是否已经连通
cin >> q;
while(q--){
int x,y;
cin >> x >> y;
if(che(x,y)){
cout << "Yse" << endl;
}
else{
cout << "No" << endl;
}
}
return 0;
}
如果想要做最小生成树,只要将输入的边保存下来,然后排序,一个个输入,直到五个结点都在同一个集合中,对上面程序做简要的添加删除即可。