Boruvka's - HolmesJJ/Data-Structures-and-Algorithms GitHub Wiki

详解

算法: 最小生成树 学习笔记 - Boruvka 生成树算法

核心思想

• 贪婪算法
• 普里姆Prim算法和克鲁斯克尔Kruskal算法的综合，每次迭代同时扩展多棵子树，直到得到最小生成树

算法步骤（最小生成树分区Partition属性 + 无环属性）

1. 把图所有的边都移除，并都放到一个优先队列中，按照边权从小到大排列（克鲁斯克尔Kruskal's）
2. 把每个结点都作为一个组件Partition，对于每个组件Partition都找其相邻权重最小的边，将这些边添加到组件Partition上，若出现环，就把该边丢弃，不断重复直到所有的结点都能被访问（普里姆Prim's）

标准写法

要点

• 维护一个表储存边权，每次需要找到边权最小的边，优先队列或AVL树搜索的时间复杂度是0(logn)