要么改变世界,要么适应世界
该标签下的文章

利用并查集求最小生成树

2020-04-10 22:52:00
99
算法

## 什么是 Kruskal 算法? **Kruskal** 算法是求最小生成树的一种方法,有点类似于贪心算法,首先是按照边的权值从小到大进行排序,然后不断地将较小的边加入到过程解的集合,关键是要解决回路的问题,而利用并查集就可以很好地解决这个问题,即每次添加边之前,判断该边的两个顶点是否是处于相同的集合,相同就跳过,否则加入到过程解中,重复这个过程,知道最后只有一个集合,该集合即为所求。<!--more--> ...