村村通工程kruskal算法python代码实现

以下是村村通工程的Kruskal算法Python代码实现：

# 定义边类
class Edge:
    def __init__(self, u, v, w):
        self.u = u
        self.v = v
        self.w = w
    
    def __lt__(self, other):
        return self.w < other.w

# 定义并查集类
class UnionFind:
    def __init__(self, n):
        self.parent = list(range(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):
        self.parent[self.find(x)] = self.find(y)

# 定义Kruskal算法函数
def kruskal(n, edges):
    edges.sort()
    uf = UnionFind(n)
    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为边的列表，每一条边的起点、终点、权值分别为u、v、w。函数返回最小生成树的边集。