7-2 最小生成树-kruskal (40 分)

• • 7-2 最小生成树-kruskal (40 分)
• 前言
• 一、题
• • 1.最小生成树-kruskal
  • 2.注意点
• 二、解
• • 1.过程
  • 2.代码
  • 3.结果

克鲁斯卡尔（Kruskal）算法其基本思想是：假设连通网G=（V，E），令最小生成树的初始状态为只有n个顶点而无边的非连通图T=（V，{}），概述图中每个顶点自成一个连通分量。在E中选择代价最小的边，若该边依附的顶点分别在T中不同的连通分量上，则将此边加入到T中；否则，舍去此边而选择下一条代价最小的边。依此类推，直至T中所有顶点构成一个连通分量为止 。

注意点： 用c写，并使用数组存储时，因为数组太长，出现运行超时的情况，如下

所以如要使用数组写 ，使用c++即可

过程如下：
1.将每个点当作一棵树，所有点组成森林
2.给每条边排序，小的在前，大的在后，方便使用
3.每次找最小的边，先判断这条边的两个点是否在同一颗树中，若在，则判断下一条边；若不在，将该点与另一个点相连，即改变他的父节点。将每次成功时的边的长度加起来，得到的便是结果。

c++代码如下:

#include
#include
#include
using namespace std;
struct Edge
{
    int x,y,z;
}a[1000010]; //存储x,y,z的信息
bool cmp(const Edge &a,const Edge &b)//比较大小
{
        return a.z 
3.结果 

 202110111729一