Kruskal算法实现代码

Kruskal算法是一种用于解决最小生成树问题的贪心算法，其基本思路是：将所有边按照权值从小到大排序，然后依次选取权值最小的边，如果这条边连接的两个顶点不在同一个连通块中，则选取这条边，并将这两个顶点所在的连通块合并。

以下是Kruskal算法的实现代码：

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):
        px, py = self.find(x), self.find(y)
        if px != py:
            self.parent[px] = py

def kruskal(n, edges):
    uf = UnionFind(n)
    edges.sort(key=lambda x: x[2])
    res = []
    for u, v, w in edges:
        if uf.find(u) != uf.find(v):
            uf.union(u, v)
            res.append((u, v, w))
    return res

其中，UnionFind类用于维护连通性，kruskal函数接收一个图的节点数n和边列表edges，返回最小生成树的边列表res。