两个连通分量的时候，我们就已将权值进行相加，那么这样的结果是最小生成树

3.那么我们就需要对边进行升序排序了，按顺序每次选取最小的边

4.这里考虑到还要对权值进行升序处理，而且是按一组数据中的某个元素 升序处理

那么这里我们就不再用邻接矩阵和邻接表来存数据了，用结构体数组来存每组数据

同时通过重写sort方法来处理升序问题

5.那么通过上方的分析你还有另外一个收获，判断图是否连通，哈哈哈，如果最后的father数组

中每个结点的根节点都是同一个值 那么说明他是连通的 （这里的结点指的是father数组当中的下标）

五：上码

===================================================================

/**

思路：

1.用kruskal算法是从边的角度出发的每次选取最小的边

2.这里涉及到并查集，回归到本题就是先将每个顶点当成一个联通分量（也是一棵树）

并设置其父节点都为 -1，表示根节点，如果两个连通分量根节点不同，那么将其合并，

同时更新其中一个连通分量的根节点为另一个连通分量的根节点

那么到最后就会形成一个根节点，此时图的各个结点也是连通的，我们在每次计算是否合并

两个连通分量的时候，我们就已将权值进行相加，那么这样的结果是最小生成树

3.那么我们就需要对边进行升序排序了，按顺序每次选取最小的边

4.这里考虑到还要对权值进行升序处理，而且是按一组数据中的某个元素 升序处理

那么这里我们就不再用邻接矩阵和邻接表来存数据了，用结构体数组来存每组数据

同时通过重写sort方法来处理升序问题

5.那么通过上方的分析你还有另外一个收获，判断图是否连通，哈哈哈，如果最后的father数组

只输出一个值 那么说明他是连通的

*/

#include<bits/stdc++.h>

using namespace std;

#define maxx 1000010//这里需要7位数

//定一结构体数组来存每组数据

struct Node{

int from;

int to;

int val;

}node[maxx];

int father[maxx];

bool sort_val(Node a,Node b){

return a.val < b.val;

}

//查询元素的根节点

int find( int a ){

int r=a;

while(father[r]!=r)

r=father[r]; //找到他的前导结点

int i=a,j;

while(i!=r){ //路径压缩算法

j=father[i]; //记录x的前导结点

father[i]=r; //将i的前导结点设置为r根节点

i=j;

}

return r;

}

//合并根节点不同的联通分量

void merg(int a,int b){

// int a = find(x);//查询x的根节点

// int b = find(y);//查询y的根节点

// if(a != b){

father[a] = b;

// }

}

int main(){

int n,m;

int sum = 0;

//cin >> n >> m;

scanf(“%d%d”,&n,&m);

//初始化father数组 将其每个顶点的根节点设置为自己的节点号

for(int i = 1; i <= n; i++){

father[i] = i;

}

for(int i = 0; i < m; i++){

//cin >> node[i].from >> node[i].to >> node[i].val;

scanf(“%d%d%d”,&node[i].from,&node[i].to,&node[i].val);

}

sort(node,node+m,sort_val);

// for(int i = 0; i < m; i++){

// cout << node[i].val << endl;

// }

int count = 0;

for(int i = 0; i < m; i++){

if(count == n - 1){//n个顶点需要 n - 1边

break;

}

int a = find(node[i].from);

int b = find(node[i].to);

if(a != b){

father[a] = b;

sum += node[i].val;

count++;

}

}

printf(“%d”,sum);

// cout << sum;

}

六：知识速递（对并查集不了解的兄弟们可以了解下）

=======================================================================================

这道题用到了并查集，所以我就学了一下并查集，所以把自己的见解也分享给大家（建议 先看视频 再浏览 博客 再自己敲一遍 学习效率高而已，我总是乱着来 以为看几篇博客就会了，其实最后还是老老实实 去B站看大佬讲解视频 才搞懂）

1:并查集

---

并查集是一种树型的数据结构，

用于处理一些不相交集合（Disjoint Sets）的合并及查询问题

1：查询元素a和元素b是否属于同一组

2：合并元素a和元素b所在组 （将有相同元素的元素 合并为一个组 ）

自我介绍一下，小编13年上海交大毕业，曾经在小公司待过，也去过华为、OPPO等大厂，18年进入阿里一直到现在。

深知大多数Java工程师，想要提升技能，往往是自己摸索成长或者是报班学习，但对于培训机构动则几千的学费，着实压力不小。自己不成体系的自学效果低效又漫长，而且极易碰到天花板技术停滞不前！

因此收集整理了一份《2024年Java开发全套学习资料》，初衷也很简单，就是希望能够帮助到想自学提升又不知道该从何学起的朋友，同时减轻大家的负担。

既有适合小白学习的零基础资料，也有适合3年以上经验的小伙伴深入学习提升的进阶课程，基本涵盖了95%以上Java开发知识点，真正体系化！

由于文件比较大，这里只是将部分目录截图出来，每个节点里面都包含大厂面经、学习笔记、源码讲义、实战项目、讲解视频，并且会持续更新！

如果你觉得这些内容对你有帮助，可以扫码获取！！（备注Java获取）

读者福利

由于篇幅过长，就不展示所有面试题了，感兴趣的小伙伴

更多笔记分享

《互联网大厂面试真题解析、进阶开发核心学习笔记、全套讲解视频、实战项目源码讲义》点击传送门即可获取！
伴**

[外链图片转存中…(img-cf6HCO1N-1712560797664)]

[外链图片转存中…(img-8iuy0fTJ-1712560797664)]

[外链图片转存中…(img-YYiV735S-1712560797664)]

更多笔记分享

[外链图片转存中…(img-v3rTPVa3-1712560797664)]
《互联网大厂面试真题解析、进阶开发核心学习笔记、全套讲解视频、实战项目源码讲义》点击传送门即可获取！