最小生成树kruskal算法，python实现

Kruskal算法是一种贪心算法，用于求解带权无向连通图的最小生成树问题。Kruskal算法的基本思路是：将所有边按照边权从小到大排序，然后依次加入到最小生成树中，如果加入该边会形成环，则舍弃该边。

下面是Kruskal算法的Python实现：

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(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):
        self.parent[self.find(i)] = self.find(j)

def kruskal(n, edges):
    uf = UnionFind(n)
    edges.sort(key=lambda e: e)
    res = []
    for e in edges:
        if uf.find(e) != uf.find(e):
            uf.union(e, e)
            res.append(e)
        if len(res) == n - 1:
            break
    return res

其中，`UnionFind`是并查集数据结构，用于维护连通性。`kruskal`函数的输入参数为节点数`n`和边集`edges`，输出为最小生成树的边集。