kruskal算法实现最小生成树的python代码

以下是使用Kruskal算法实现最小生成树的Python代码示例：

# 定义边的类
class Edge:
    def __init__(self, src, dest, weight):
        self.src = src
        self.dest = dest
        self.weight = weight

# 定义并查集类
class UnionFind:
    def __init__(self, vertices):
        self.parent = {}
        self.rank = {}

        for v in vertices:
            self.parent[v] = v
            self.rank[v] = 0

    def find(self, v):
        if self.parent[v] != v:
            self.parent[v] = self.find(self.parent[v])
        return self.parent[v]

    def union(self, v1, v2):
        root1 = self.find(v1)
        root2 = self.find(v2)

        if self.rank[root1] < self.rank[root2]:
            self.parent[root1] = root2
        elif self.rank[root1] > self.rank[root2]:
            self.parent[root2] = root1
        else:
            self.parent[root2] = root1
            self.rank[root1] += 1

# 定义最小生成树函数
def kruskal(graph):
    result = []

    # 将图的边按权重排序
    graph.sort(key=lambda x: x.weight)

    # 获取图中的所有顶点
    vertices = set()
    for edge in graph:
        vertices.add(edge.src)
        vertices.add(edge.dest)

    # 创建并查集
    uf = UnionFind(vertices)

    # 遍历图的边
    for edge in graph:
        root1 = uf.find(edge.src)
        root2 = uf.find(edge.dest)

        # 如果两个顶点的根节点不同，则将边加入最小生成树中
        if root1 != root2:
            result.append(edge)
            uf.union(root1, root2)

    return result

# 示例用法
graph = [
    Edge('A', 'B', 4),
    Edge('A', 'H', 8),
    Edge('B', 'C', 8),
    Edge('B', 'H', 11),
    Edge('C', 'D', 7),
    Edge('C', 'F', 4),
    Edge('C', 'I', 2),
    Edge('D', 'E', 9),
    Edge('D', 'F', 14),
    Edge('E', 'F', 10),
    Edge('F', 'G', 2),
    Edge('G', 'H', 1),
    Edge('G', 'I', 6),
    Edge('H', 'I', 7)
]

minimum_spanning_tree = kruskal(graph)

for edge in minimum_spanning_tree:
    print(f"{edge.src} - {edge.dest}: {edge.weight}")