Kruskal的python代码

Kruskal算法是一种用于求解最小生成树的贪心算法。下面是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 root1 != root2:
            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

# Kruskal算法实现
def kruskal(vertices, edges):
    # 根据边的权重对边进行排序
    edges.sort(key=lambda x: x.weight)
    
    # 创建并查集对象
    uf = UnionFind(vertices)
    
    # 存储最小生成树的边
    mst = []
    
    for edge in edges:
        src_root = uf.find(edge.src)
        dest_root = uf.find(edge.dest)
        
        # 如果边的两个顶点不在同一个连通分量中，则将边加入最小生成树
        if src_root != dest_root:
            mst.append(edge)
            uf.union(src_root, dest_root)
    
    return mst

# 测试代码
vertices = ['A', 'B', 'C', 'D', 'E']
edges = [
    Edge('A', 'B', 4),
    Edge('A', 'C', 1),
    Edge('B', 'C', 3),
    Edge('B', 'D', 2),
    Edge('C', 'D', 4),
    Edge('C', 'E', 5),
    Edge('D', 'E', 1)
]

mst = kruskal(vertices, edges)
for edge in mst:
    print(f"{edge.src} - {edge.dest}: {edge.weight}")