kruskal算法求最小生成树代码python

以下是Kruskal算法的Python代码：

class Edge:
    def __init__(self, u, v, weight):
        self.u = u
        self.v = v
        self.weight = weight

def kruskal(n, edges):
    parent = [i for i in range(n)]
    rank = [0]*n
    edges.sort(key=lambda x: x.weight)
    result = []
    for e in edges:
        u_root = find(parent, e.u)
        v_root = find(parent, e.v)
        if u_root != v_root:
            result.append(e)
            if rank[u_root] > rank[v_root]:
                parent[v_root] = u_root
            elif rank[u_root] < rank[v_root]:
                parent[u_root] = v_root
            else:
                parent[u_root] = v_root
                rank[v_root] += 1
    return result

def find(parent, node):
    if parent[node] == node:
        return node
    parent[node] = find(parent, parent[node])
    return parent[node]

其中 `Edge` 类表示一条边，`kruskal` 函数接受节点数 `n` 和边列表 `edges`，返回最小生成树的边列表 `result`。`find` 函数实现了路径压缩的并查集，用于判断两个节点是否在同一集合中。