Kurskal算法求最小生成树python

以下是使用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, i):
        if self.parent[i] != i:
            self.parent[i] = self.find(self.parent[i])
        return self.parent[i]

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

# Kruskal算法求最小生成树
def kruskal(n, edges):
    edges.sort(key=lambda e: e.w)
    uf = UnionFind(n)
    mst = []
    for e in edges:
        if uf.union(e.u, e.v):
            mst.append(e)
        if len(mst) == n - 1:
            break
    return mst

其中，n 表示图中的节点数，edges 是一个由 Edge 类型的对象组成的列表，每个 Edge 对象包含三个属性：起点 u，终点 v 和边权 w。函数 kruskal 返回一个列表，包含最小生成树上的边。