最小生成树之Kruskal算法

学习数据结构与算法
2021-05-17 14:29 · 阅读时长5分钟
小课

Kruskal算法是一种最小生成树算法,他通过不断选择权值最小的边来构成一棵树,所以叫做加边法。

主要思路是,首先将所有的边按从小到大排序,然后不断选取其中最小且与当前树不构成环路的边,直到选择v-1条边,v是顶点个数,其中需要判断边的加入是否会导致环路,是通过并查集1来实现的。

查看并查集的课程

注释
加载中...
加载中...
Kruskal最小生成树加边法