Boruvka 生成树算法
2020-12-19 17:39
阅读：577
标签：思想 其他 while prim class 不同 lang lan 方式 Boruvka 算法的一句话思想便是： “从所有当前的连通块向其他连通块扩展出最小边，直到只剩一个连通块”，其中取最小边的贪心思想是 Kruskal 的主体，而向外扩展又是 Prim 的思想 —— 基于另外两种生成树算法，Boruvka 的正确性显然。 代码框架: 就是val[i]的求解会用其他方式辅助求解，在对于给出一种计算两点之间边权的方式的题目下相当好用 Boruvka 生成树算法 标签：思想 其他 while prim class 不同 lang lan 方式 原文地址：https://www.cnblogs.com/graytido/p/13378141.htmlBoruvka 生成树算法
while 连通块个数>1
for 每个连通块 i
val[i] = 连接 i 与其他连通块的最小边
for 每个连通块 i
if val[i] 连接两个不同的连通块
ans += val[i]
Merge( val[i] 连接的连通块 )
连通块个数 --
上一篇：Java Object类
下一篇：快速排序
评论
亲，登录后才可以留言！