Boruvka's
Hu JiaJun edited this page Apr 21, 2021
·
3 revisions
算法: 最小生成树
学习笔记 - Boruvka 生成树算法
- 贪婪算法
- 普里姆Prim算法和克鲁斯克尔Kruskal算法的综合,每次迭代同时扩展多棵子树,直到得到最小生成树
- 把图所有的边都移除,并都放到一个优先队列中,按照边权从小到大排列(克鲁斯克尔Kruskal's)
- 把每个结点都作为一个组件Partition,对于每个组件Partition都找其相邻权重最小的边,将这些边添加到组件Partition上,若出现环,就把该边丢弃,不断重复直到所有的结点都能被访问(普里姆Prim's)
- 维护一个表储存边权,每次需要找到边权最小的边,优先队列或AVL树搜索的时间复杂度是0(logn)