用kruskal最小生成树python

Kruskal算法是一种用于求解最小生成树的算法，它的基本思想是将所有边按照权值从小到大排序，然后依次加入到生成树中，如果加入一条边会形成环，则不加入该边，直到生成树中有n-1条边为止。

在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 = [] * 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):
    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)
            if len(res) == n - 1:
                break
    return res

其中，Edge类表示边，包含起点、终点和权值三个属性；UnionFind类表示并查集，包含find和union两个方法；kruskal函数是Kruskal算法的实现，输入参数为节点数n和边集edges，输出最小生成树的边集res。