kruskal算法python

是使用Python实现Kruskal算法的示例代码：

# 定义边的类
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 self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y):
        px, py = self.find(x), self.find(y)
        if px == py:
            return False
        if self.rank[px] < self.rank[py]:
            self.parent[px] = py
        elif self.rank[px] > self.rank[py]:
            self.parent[py] = px
        else:
            self.parent[py] = px
            self.rank[px] += 1
        return True

# 定义Kruskal算法函数
def kruskal(n, edges):
    uf = UnionFind(n)
    edges.sort(key=lambda e: e.w)
    res = []
    for e in edges:
        if uf.union(e.u, e.v):
            res.append(e)
    return res

其中，`Edge`类表示一条边，包含起点、终点和权值三个属性；`UnionFind`类表示并查集，包含`find`和`union`两个方法；`kruskal`函数接受节点数`n`和边的列表`edges`作为输入，返回最小生成树的边的列表。