如果说prim算法是通过扩展点来求最小生成树，那么kruskal就是通过扩展边的方式来进行。
算法主体：
1：对所有的边按边权从小到大进行排序
2：选取未被标记的边，如果边的两个顶点不在一个集合中，就合并他们所在的两个集合，如果在一个集合中，则不需要操作。然后标记此边
3：重复2，直到所有点都在一个集合中
举个例子（图源网络）
image.png
先排序：3 4 5 6 6 7 8 9 12
首先找到最小的边3，他的两端是2和3，连起来
image.png
然后是最小的边4，他的两端是1和2，连起来
image.png
以此类推
image.png
第四条边的两端是4和3，发现他们已经在一个集合中了，直接去下一个边
第五条边的两端是1和5，连起来
image.png
第⑥条边的两端是7和5，连起来
image.png
第7条边的两端是7和6，连起来，截止到目前，我们发现所有点都进入了集合，好了，算法结束，最小生成树已经被找到了
image.png
我觉得这个思想已经很清晰了，下面我们来结合题目看看代码是如何进行实现的
前置：并查集（之前都有讲）
image.png
很显然就是求一个最小生成树，还要特别判断是否连通
#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;
struct xing
{
int tou,wei,quan;//存边的，分别是边的两个端点和边权
}bian[201000];
int n,m,pre[11000],o1,o2,ant;//pre数组用于存储点的祖宗节点，ans是总边权，ant表示有几个边被选中
long long ans;//开大点防止越界
bool cmp(xing a,xing b)
{
return a.quan<b.quan;//比较函数，看不懂的自己百度
}
int find(int u)
{
int r=u;
if(u!=pre[u])
r=find(pre[u]);
return pre[u]=r;//压缩路径并查集，前面一篇讲过了
}
int main()
{
cin>>n>>m;//输入n和m的信息
for(int i=1;i<n+1;i++)
pre[i]=i;//初始化并查集，所有点的祖宗都是自己
for(int i=1;i<m+1;i++)
{
cin>>bian[i].tou>>bian[i].wei>>bian[i].quan;//输入边的信息
}
sort(bian+1,bian+1+m,cmp);//快排从小到大排序
for(int i=1;i<m+1;i++)//遍历开始
{
o1=find(bian[i].tou);
o2=find(bian[i].wei);
if(o1!=o2)//如果不在一个集合
{
pre[o1]=o2;//合并集合
ans+=bian[i].quan;//加边权
ant++;//边数++
}
}
if(ant!=n-1)//根据树的特性，n个点的应该有n-1条边，如果不是，说明不是树
cout<<"orz";
else
cout<<ans;
}
好了，这篇就这样吧，图论基础算法也就这些了，下篇再见
