最小生成树是数据结构中一个经典的问题,一次在刷题的过程中遇到了这类的问题,那时候遇到这类问题就很迷茫。建立最小生成树有两种方法,一种是以点建树,每次都选择最近的点,即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;
}

如果想要做最小生成树,只要将输入的边保存下来,然后排序,一个个输入,直到五个结点都在同一个集合中,对上面程序做简要的添加删除即可。