最小生成树算法：Boruvka算法

Boruvka算法详解

Boruvka算法（也译作博鲁夫卡算法）是最早的最小生成树（MST）算法（1926年提出），同样基于贪心策略，核心思想是：每次为每个连通分量选择权值最小的出边，合并分量，重复此过程直到所有顶点归为一个连通分量。

该算法的独特优势是适合分布式计算和处理图的动态连通性，也是唯一能高效处理“边权随时间变化”或“增量式MST”场景的MST算法。

资料：https://pan.quark.cn/s/43d906ddfa1b、https://pan.quark.cn/s/90ad8fba8347、https://pan.quark.cn/s/d9d72152d3cf

一、核心概念

二、算法步骤

三、核心难点：找每个分量的最小出边

对每条边 (u, v, w)，若 u 和 v 属于不同分量：

• 比较 w 与 u 所在分量的当前最小出边权值，若更小则更新；
• 同理比较 w 与 v 所在分量的当前最小出边权值，若更小则更新。

四、代码实现（Python）

结合并查集管理连通分量，高效实现分量合并与最小出边查找：

class UnionFind:
"""并查集（路径压缩 + 按秩合并），管理连通分量"""
def __init__(self, n):
self.parent = list(range(n)) # 父节点
self.rank = [1] * n # 分量大小（秩）

def find(self, x):
"""查找根节点，路径压缩"""
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]

def union(self, x, y):
"""合并两个分量，返回是否合并成功"""
root_x = self.find(x)
root_y = self.find(y)
if root_x == root_y:
return False
# 按秩合并
if self.rank[root_x] > self.rank[root_y]:
self.parent[root_y] = root_x
self.rank[root_x] += self.rank[root_y]
else:
self.parent[root_x] = root_y
self.rank[root_y] += self.rank[root_x]
return True

def boruvka(n, edges):
"""
Boruvka算法求最小生成树
:param n: 顶点数（0~n-1）
:param edges: 边列表，格式为[(u, v, weight), …]
:return: (MST的边列表, 总权值)，若无MST返回([], -1)
"""
uf = UnionFind(n)
mst_edges = []
total_weight = 0
num_components = n # 初始连通分量数为顶点数

while num_components > 1:
# 步骤1：初始化每个分量的最小出边（格式：{根节点: (u, v, w)}）
min_edge = {}
for u, v, w in edges:
root_u = uf.find(u)
root_v = uf.find(v)
if root_u == root_v:
continue # 同一分量，跳过

# 更新u所在分量的最小出边
if root_u not in min_edge or w < min_edge[root_u][2]:
min_edge[root_u] = (u, v, w)
# 更新v所在分量的最小出边
if root_v not in min_edge or w < min_edge[root_v][2]:
min_edge[root_v] = (u, v, w)

# 步骤2：若无最小出边，图不连通
if not min_edge:
return [], –1

# 步骤3：合并分量，加入MST
added_edges = set() # 避免重复添加同一条边
for root in min_edge:
u, v, w = min_edge[root]
# 用边的元组去重（避免(u,v)和(v,u)重复）
edge_tuple = tuple(sorted((u, v))) + (w,)
if edge_tuple in added_edges:
continue
# 合并分量
if uf.union(u, v):
mst_edges.append((u, v, w))
total_weight += w
num_components -= 1
added_edges.add(edge_tuple)

# 步骤4：若本次迭代未合并任何分量，终止（图不连通）
if not added_edges:
return [], –1

return mst_edges, total_weight

# 测试示例
if __name__ == "__main__":
# 顶点数：4（0,1,2,3）
n = 4
# 边列表：(u, v, weight)
edges = [
(0, 1, 1),
(0, 2, 3),
(1, 2, 1),
(1, 3, 4),
(2, 3, 1)
]
mst, weight = boruvka(n, edges)
print("最小生成树的边：", mst)
print("总权值：", weight)
# 输出：
# 最小生成树的边： [(0, 1, 1), (1, 2, 1), (2, 3, 1)]（顺序可能略有不同）
# 总权值： 3

五、算法分析

六、Boruvka vs Kruskal vs Prim

七、关键注意点

八、进阶应用

• 处理大规模图：Boruvka算法可分布式实现，每个节点负责计算自身所在分量的最小出边，适合分布式系统；
• 增量式MST：当图中新增边时，只需重新计算受影响分量的最小出边，无需完全重构MST；
• 多最小生成树：可通过修改“最小出边”的选择规则（如选次小边），找出所有可能的MST。