python实现kruskal

Kruskal算法是一种用于计算最小生成树的算法。下面是Python代码实现：

# 定义一个边类
class Edge:
    def __init__(self, u, v, w):
        self.u = u
        self.v = v
        self.w = w

# 定义一个并查集类
class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n

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

    def union(self, x, y):
        root_x, root_y = self.find(x), self.find(y)
        if root_x == root_y:
            return False
        if self.rank[root_x] < self.rank[root_y]:
            root_x, root_y = root_y, root_x
        self.parent[root_y] = root_x
        if self.rank[root_x] == self.rank[root_y]:
            self.rank[root_x] += 1
        return True

def kruskal(n, edges):
    # 对边按权值从小到大排序
    edges.sort(key=lambda x: x.w)
    uf = UnionFind(n)
    res = []
    for e in edges:
        if uf.union(e.u, e.v):
            res.append(e)
    return res

其中，`n`表示节点数，`edges`是一个边列表，每个边包含起点、终点和权值。算法的核心是对边按权值从小到大排序，然后依次加入到生成树中，如果加入一条边会形成环，则跳过该边。最终返回生成树的边列表。