最小生成树克鲁斯卡尔算法代码

以下是使用并查集实现的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 = [i for i in range(n)]
        self.rank = [1] * n
    
    # 查找x所在的连通块的根节点
    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
    
    # 合并x和y所在的连通块
    def union(self, x, y):
        root_x, root_y = self.find(x), self.find(y)
        if root_x == root_y:
            return
        if self.rank[root_x] < self.rank[root_y]:
            self.parent[root_x] = root_y
        elif self.rank[root_x] > self.rank[root_y]:
            self.parent[root_y] = root_x
        else:
            self.parent[root_x] = root_y
            self.rank[root_y] += 1

# 定义Kruskal算法函数
def kruskal(n, edges):
    uf = UnionFind(n)
    edges.sort(key=lambda e: e.w)  # 按边权从小到大排序
    res = []
    for e in edges:
        if uf.find(e.u) != uf.find(e.v):  # 不在同一个连通块中
            uf.union(e.u, e.v)
            res.append(e)
    return res

其中n为顶点的数量，edges是存储边的列表，每个元素是一个Edge对象。kruskal函数返回的是最小生成树的边集合，也就是一个包含若干个Edge对象的列表。