Kruskal算法是图论中用来求解无向连通图最小生成树的常用方法。它采用贪心策略，从权值最小的边开始选，保证每次加入的边不与已选边构成回路，最终用n减1条边连接全部n个顶点且总权值最小。判断回路通常借助并查集完成，整体思路清晰、编码简单。
Kruskal算法是什么
最小生成树是指在一个带权连通图中，选取一个包含所有顶点的子图，该子图是一棵树且边权总和最小。Kruskal算法由Joseph Kruskal提出，属于贪心算法：先把所有边按权重升序排列，再从小到大扫描，若当前边连接的两个顶点不在同一个连通块中，就把它加入结果集，否则跳过。当加入边数达到顶点数减一时结束。
Kruskal的实现步骤
基本流程
- 输入图的所有边，每条边包含起点、终点和权值
- 将边按权值从小到大排序
- 初始化并查集，每个顶点自成一个集合
- 依次遍历排序后的边，用并查集检查两端点是否同根
- 若不同根则合并集合并收录该边，同根则忽略
- 收录边数量等于顶点数减一时停止
并查集辅助函数
并查集需要支持查找根节点和合并两个集合，常配合路径压缩与按秩合并提升效率。
代码示例
下面给出Python语言实现的Kruskal算法完整示例：
# 并查集实现
class UnionFind:
def __init__(self, n):
self.parent = list(range(n)) # 父节点初始指向自己
self.rank = [0] * 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):
rx, ry = self.find(x), self.find(y)
if rx == ry:
return False # 已在同一集合
if self.rank[rx] < self.rank[ry]:
self.parent[rx] = ry
elif self.rank[rx] > self.rank[ry]:
self.parent[ry] = rx
else:
self.parent[ry] = rx
self.rank[rx] += 1
return True
# Kruskal算法主函数
def kruskal(edges, n):
# edges: 列表，元素为(权值, 起点, 终点)
edges.sort(key=lambda e: e[0]) # 按权值升序
uf = UnionFind(n)
result = []
for w, u, v in edges:
if uf.union(u, v):
result.append((u, v, w))
if len(result) == n - 1:
break
return result
# 测试：4个顶点，边为(权值,起点,终点)
edges = [(1, 0, 1), (2, 1, 2), (3, 2, 3), (4, 0, 2), (5, 1, 3)]
mst = kruskal(edges, 4)
print("最小生成树边：", mst)
复杂度与注意事项
若图有e条边、n个顶点，排序耗时O(e log e)，并查集操作近似O(e α(n))，总体约为O(e log e)。使用Kruskal时应注意顶点编号从0开始或做映射，且图必须连通才能得到完整最小生成树，非连通图只能得到最小生成森林。
Kruskal算法适合边相对稀疏的图，在边很多时Prim算法可能更优，但Kruskal代码更直观易写。
小结
理解Kruskal算法是什么以及掌握Kruskal的实现步骤，关键在于明白贪心选边与并查集判环的配合。实际编码时把边排序、并查集写好，算法就完成了大半。