Python最小生成树 Kruskal 算法
较难4用最少的钱连通所有城市——Python Kruskal 算法详解
想象一下，你是一个城市设计师，要给几个新建的居民区铺设供暖管道。每个居民区之间铺设管道的成本不同，你希望花最少的钱，让所有居民区都能通过管道连通（比如从A区可以通过B区再到C区，不需要A和C之间直接连）。这就是“最小生成树”问题——在图中找到一棵包含所有节点且边权总和最小的树。Kruskal算法就是解决这个问题的经典方法之一，它像搭积木一样，每次挑最便宜、不造成“环路”的边，直到所有点都连起来。
算法核心思想——先排序，再连接，不绕圈
Kruskal算法的核心步骤只有三步：
- 排序：把所有的边（连接两个节点的路径）按权重从小到大排序。就像把所有桥的造价从低到高排好队。
- 选边：从最便宜的边开始检查。如果这条边的两个端点还没有被连通（不在同一个集合里），就选择它，并标记这两个端点属于同一个连通块；否则跳过它。
- 停止：当选择的边数等于节点数减1时，就找到了最小生成树。因为一棵有n个节点的树恰好有n-1条边。
这个过程很像玩“俄罗斯方块”或者“积木连接”：你手里有一堆长短不一的积木条（边），每次拿起最短的那根，如果它能把两个原本不连在一起的积木块粘起来，你就用它；如果它连的两个积木块已经属于同一大块了（再连就会绕成一个环），就扔掉它。直到所有散块都合成一大块，你手里的积木条就是最短路径。
并查集——判断“是否已经连通”的神器
在Kruskal算法中，我们需要快速知道两个节点是否已经在同一个连通块中，并且当选择一条边后，需要把两个连通块合并。这就是**并查集（Union-Find）**的用武之地。它就像一个“帮派登记系统”，每个节点都属于一个“帮派”，帮派有一个“老大”作为代表。我们可以通过找“老大”来判断两个节点是不是一伙的，也可以把两个帮派合并成一个。
并查集的三个核心操作
- 初始化：每个人最初都是自己的老大。
parent数组记录每个人的上级，rank数组记录帮派的“等级”，用于优化合并。 - 查找（find）：找到某个节点的帮派老大（根节点）。路径压缩优化：找老大的路上，顺便把路上的小弟直接挂在老大名下，下次找得更快。
- 合并（union）：把两个帮派合并。先找到各自老大，如果老大不同，就把等级低的帮派合并到等级高的帮派下，保持树的平衡。
生活中的例子
假设班上有5个同学，一开始谁也不认识谁。parent记录每个同学自己（0号同学的老大是0，1号同学的老大是1……）。老师宣布：“现在开始交朋友，每次我念一对同学的名字，如果他们已经是一个朋友圈了，就跳过；否则他们就成为新朋友，合并朋友圈。”
第一次老师念：“小明和小红”。因为小明和小红的老大不同（小明老大是0号，小红老大是1号），于是合并，比如让小红的老大认小明为老大。现在小明和小红在同一朋友圈。
第二次老师念：“小红和小刚”。查一下：小红的老大是0，小刚的老大是2，不同，合并。现在0号帮派包含了小明、小红、小刚。
第三次老师念：“小明和小刚”。查一下：小明老大是0，小刚老大也是0（因为小红合并时，小刚也跟了小明），相同！这说明他们已经是一个朋友圈了，这条边会造成“环”，不能选。
这个机制正是Kruskal所需要的。
Python代码实现并查集
class UnionFind:
def __init__(self, n):
# parent: 每个节点的父节点，最初自己指向自己
self.parent = list(range(n))
# rank: 每个根节点的“高度”估计值，用于平衡树
self.rank = [0] * n
def find(self, x):
# 查找节点x的根节点，同时做路径压缩
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def union(self, x, y):
# 合并x和y所在的集合，若已在同一集合返回False，否则返回True
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_x] = root_y
elif self.rank[root_x] > self.rank[root_y]:
self.parent[root_y] = root_x
else:
self.parent[root_y] = root_x
self.rank[root_x] += 1 # 高度相等时，合并后高度+1
return True
Kruskal主算法——搭积木的过程
有了并查集，Kruskal算法就很简单了：
- 将所有边按照权重排序（权重就是修路/架桥的成本）。
- 初始化并查集，节点从0到n-1。
- 依次遍历排好序的边。对每条边(u, v, weight)，调用
union：- 如果返回
True，说明这条边连接了两个不同的连通块，选它！增加总权重，把它记录下来。 - 如果返回
False，说明会形成环，跳过。
- 如果返回
- 当选中边的数量达到
n-1时，提前结束，因为已经形成了一棵完整的树。
完整可运行的示例代码
下面我们用5个城市（节点0~4）和7条可能的道路（边）来演示。边用元组(权重, 起点, 终点)表示。
class UnionFind:
def __init__(self, n):
# parent: 每个节点的父节点，初时自己指向自己
self.parent = list(range(n))
# rank: 每个根节点的高度估计
self.rank = [0] * n
def find(self, x):
# 查找x的根节点（路径压缩）
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def union(self, x, y):
# 合并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_x] = root_y
elif self.rank[root_x] > self.rank[root_y]:
self.parent[root_y] = root_x
else:
self.parent[root_y] = root_x
self.rank[root_x] += 1
return True
def kruskal_mst(n, edges):
"""
计算最小生成树
:param n: 节点个数（0 ~ n-1）
:param edges: 边列表，每个元素是 (weight, u, v)
:return: (总权重, 选中的边列表)
"""
# 按权重从小到大排序
edges.sort()
# 创建并查集
uf = UnionFind(n)
# 总权重初始为0
mst_weight = 0
# 记录选中的边
mst_edges = []
# 遍历所有边
for weight, u, v in edges:
# 尝试合并u和v，如果成功说明这条边可以选
if uf.union(u, v):
mst_weight += weight
mst_edges.append((u, v, weight))
# 当选中边数达到 n-1，提前结束
if len(mst_edges) == n - 1:
break
return mst_weight, mst_edges
# ---------- 示例：5个城市修路 ----------
# 节点数量
node_count = 5
# 道路列表：(造价, 城市A, 城市B)
road_list = [
(10, 0, 1), # 0-1 造价10
(15, 0, 2), # 0-2 造价15
(5, 1, 2), # 1-2 造价5
(12, 1, 3), # 1-3 造价12
(8, 2, 3), # 2-3 造价8
(7, 2, 4), # 2-4 造价7
(3, 3, 4) # 3-4 造价3
]
total_cost, used_roads = kruskal_mst(node_count, road_list)
print("最小生成树总成本:", total_cost)
print("选中的道路（城市A, 城市B, 造价）:", used_roads)
运行结果：
最小生成树总成本: 23
选中的道路（城市A, 城市B, 造价）: [(3, 3, 4), (5, 1, 2), (7, 2, 4), (10, 0, 1)]
解释：我们选了造价3、5、7、10的四条路，总成本23，连通了所有5个城市。注意造价8的那条路（2-3）没选，因为当它被检查时，节点2和3已经在同一个连通块里了（通过2-4-3已连通），再选就会形成环。
新手容易犯的错误
- 忘记排序：直接按输入顺序处理边，结果肯定不是最小生成树。排序是Kruskal算法的前提。
- 混淆节点编号：并查集中的节点编号必须从0开始连续，如果实际节点是“A、B、C”，要先映射成0、1、2。
- 忘记检查len(mst_edges) == n-1：虽然最后总会退出循环，但提前终止可以提高效率，否则会继续检查后面的边，虽然不影响结果但浪费。
- 并查集路径压缩不彻底：如果
find函数忘了递归更新parent，会导致多次查找变慢。一定要用self.parent[x] = self.find(self.parent[x])。 - 把边的权重和节点搞反：在变元组中，通常约定
(weight, u, v)，如果写成(u, v, weight)，排序时就会按节点编号排序，完全错误。 - 未考虑图不连通的情况：Kruskal算法假设图是连通的，如果最后选中的边数小于n-1，说明原图不连通，没有最小生成树。实际编程中应该对这种情况进行报错处理。
相关知识点指引
- Prim算法：另一种求最小生成树的算法，从任意点开始，每次找权重最小的边向外扩展，适合稠密图。
- 最短路径算法（Dijkstra、Bellman-Ford）：最小生成树关心所有点连通的总代价，而最短路径关心两个特定点之间的最小代价，两者容易混淆。
- 并查集优化：路径压缩和按秩合并可以使并查集操作近乎常数时间。
- 图论基础：理解图的表示（邻接矩阵、邻接表）、连通分量、树的性质（n个节点n-1条边）是学习Kruskal的前提。
如果你掌握了Kruskal算法，还可以尝试解决更多实际问题，比如：城市供水管网设计、电路布线、网络布线等——只要把“连接成本”抽象为权重，就能用这个算法找到最省钱的方案。
例题精讲
在Kruskal算法中，通常使用哪种数据结构来检测是否形成环？
Kruskal算法中，对边按权重排序的时间复杂度是？
Kruskal算法一定能得到最小生成树，即使图中存在权值相同的边。
Kruskal算法每一步选择当前权值最小的边，并保证不形成环，这是一种贪心策略。
def kruskal(n, edges):
parent = list(range(n))
rank = [0]*n
def find(x):
if parent[x] != x:
parent[x] = find(parent[x])
return parent[x]
def union(x, y):
# 按秩合并的代码略
pass
edges.sort(key=lambda e: e[2])
mst = []
for u, v, w in edges:
if ___ : # 检查u和v是否已连接
mst.append((u, v, w))
union(u, v)
if len(mst) == n-1:
break
return mst