Kruskal算法的对比prim的区别是，前者使用了并查集的思路，而后者类似于Dijkskal算法。操作策略是，对所有边权进行从小到大的排序，然后从小到大遍历所有边权去选择，一个边被选择的条件是，这条边的两个端点位于不同的集合，即二者的find函数得到的值不同，然后将两个点加到同一个集合里面即可，最后选择n – 1条边就是最小生成树
#include
#include
#include
using namespace std;
const int N = 200010;
int p[N];
int n,m;
struct Edge//边权结构体
{
int a,b,w;
bool operator< (const Edge &W)const//重载小于号，用于后面sort排序
{
return w < W.w;
}
}edges[N];
int find(int x)//并查集模板
{
if(p[x] != x) p[x] = find(p[x]);
return p[x];
}
int main()
{
scanf("%d%d",&n,&m);
for(int i = 0;i < m;i ++)
{
int a,b,w;
scanf("%d%d%d",&a,&b,&w);
edges[i] = {a,b,w};
}
sort(edges, edges + m);//对边权进行从小到的排序
for(int i = 1;i
Original: https://www.cnblogs.com/amour233/p/16483891.html
Author: LYL233
Title: Kruskal算法求最小生成树
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/643200/
转载文章受原作者版权保护。转载请注明原作者出处！