【简介】克鲁斯卡尔算法是一种用来寻找最小生成树的算法。在剩下的所有未选取的边中，找最小边，如果和已选取的边构成回路，则放弃，选取次小边。即给定一些线段的x，y和权值，当x，y不在一个集合的时候，选取权值最小的一个边，然后把x，y合并到一个集合中（并查集维护）
我们用现在来模拟一下Kruskal算法，下面给出一个无向图B,我们使用Kruskal来找无向图B的最小生成树。
首先，我们将所有的边都进行从小到大的排序。排序之后根据贪心准则，我们选取最小边(A,D)。我们发现顶点A,D不在一棵树上，所以合并顶点A,D所在的树，并将边(A,D)加入边集E。 我们接着在剩下的边中查找权值最小的边，于是我们找到的(C,E)。我们可以发现，顶点C,E仍然不在一棵树上，所以我们合并顶点C，E所在的树，并将边(C,E)加入边集E
不断重复上述的过程，于是我们就找到了无向图B的最小生成树，如下图所示!
核心代码： 初始化并查集
for (int i=1;i<=n;i++) fat[i]=i;//初始化并查集并查集中的查询和合并操作
int ask(int x){//查找是否在同一集合 if (fat[x]!=x) fat[x]=ask(fat[x]); return fat[x]; } void unite (int x,int y){ int x1=ask(x),x2=ask(y); if (x1==x2) return; else fat[x1]=x2; }另外，使用结构体存储边的x,y坐标和权值。
模板题:P3366 【模板】最小生成树 代码如下：
#include<cstdio> #include<algorithm> #define N (5010) #define M (200010) using namespace std; //定义结构体存边，x为起点，y为终点，z为值 struct edge{ int x,y,z; }a[M]; int fat[N],tot,ans; bool cmp(edge x,edge y){//用于sort的排序，按值排 return x.z<y.z; } int ask(int x){//查找是否在同一集合 if (fat[x]!=x) fat[x]=ask(fat[x]); return fat[x]; } void unite (int x,int y){ int x1=ask(x),x2=ask(y); if (x1==x2) return; else fat[x1]=x2; } int main(){ int n,m; scanf("%d%d",&n,&m); for (int i=1;i<=m;i++) scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].z); sort(a+1,a+m+1,cmp);//把边按从大到小排 for (int i=1;i<=n;i++) fat[i]=i;//初始化并查集 for (int i=1;i<=m;i++){ if (ask(a[i].x)!=ask(a[i].y)){//克鲁斯卡尔 tot++; ans=ans+a[i].z; unite(a[i].x,a[i].y); } } if (tot<n-1) printf("orz");//判断若tot=k-1则生成了最小树 else printf("%d",ans); return 0; }注意，判断若tot=k-1则生成了最小树。
