Kruskal算法详解（Python语言实现最小生成树的完整教程）

实现Kruskal算法的关键：并查集（Union-Find）

为了避免形成环，我们需要一种高效判断两个顶点是否已在同一连通分量中的数据结构——这就是并查集（Union-Find）。它支持两种操作：

• find(x)：查找元素 x 所属集合的根节点。
• union(x, y)：合并 x 和 y 所在的集合。

Python实现步骤

下面我们用Python一步步实现Kruskal算法。整个过程分为三部分：定义并查集类、定义图类、执行Kruskal算法。

1. 实现并查集（Union-Find）

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):        # 按秩合并：将低秩树合并到高秩树下        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

2. 定义图并添加边

我们可以用一个列表来存储所有的边，每条边包含 (起点, 终点, 权重)。

3. 实现Kruskal算法主函数

def kruskal(vertices, edges):    """    vertices: 顶点数量（假设顶点编号为 0 到 vertices-1）    edges: 边列表，每个元素为 (u, v, weight)    返回最小生成树的边列表及总权重    """    # 按权重升序排序所有边    edges.sort(key=lambda x: x[2])        uf = UnionFind(vertices)    mst = []  # 存储最小生成树的边    total_weight = 0        for u, v, weight in edges:        # 如果加入该边不会形成环，则加入MST        if uf.union(u, v):            mst.append((u, v, weight))            total_weight += weight            # 当MST包含 vertices-1 条边时，算法结束            if len(mst) == vertices - 1:                break        return mst, total_weight

完整示例运行

# 示例图：4个顶点，5条边vertices = 4edges = [    (0, 1, 10),    (0, 2, 6),    (0, 3, 5),    (1, 3, 15),    (2, 3, 4)]mst, total = kruskal(vertices, edges)print("最小生成树的边：")for edge in mst:    print(f"{edge[0]} -- {edge[1]} == {edge[2]}")print(f"总权重: {total}")# 输出：# 最小生成树的边：# 2 -- 3 == 4# 0 -- 3 == 5# 0 -- 1 == 10# 总权重: 19

总结

通过本教程，你已经学会了如何用Python语言实现Kruskal算法来求解最小生成树。Kruskal算法的时间复杂度主要由排序决定，为 O(E log E)，其中 E 是边的数量。配合高效的并查集结构，它能快速处理大规模图数据。

无论你是学习图论算法的新手，还是需要在项目中应用最小生成树，这个实现都能为你提供清晰的参考。动手试试吧！

关键词：Kruskal算法、最小生成树、Python实现Kruskal、图论算法