用Kruskal算法构造最小生成树

Kruskal算法是一种基于贪心思想的最小生成树算法，其基本思路是从小到大依次选取边来构造最小生成树。具体步骤如下：

1. 初始化：将每个节点看做单独的连通块。
2. 将所有边按照权值从小到大排序。
3. 依次选取边，如果这条边的两个端点不在同一个连通块中，则加入最小生成树中，并将这两个连通块合并。
4. 重复步骤3，直到最小生成树中含有n-1条边（n为图的节点数）。

下面是Kruskal算法的Python实现代码：

def kruskal(edges, n):
    # 初始化每个节点为一个单独的连通块
    parent = [i for i in range(n)]
    # 定义查找父节点的函数
    def find(x):
        if parent[x] != x:
            parent[x] = find(parent[x])
        return parent[x]
    # 定义合并连通块的函数
    def union(x, y):
        px, py = find(x), find(y)
        if px != py:
            parent[px] = py
    # 将边按权值从小到大排序
    edges.sort(key=lambda x: x[2])
    # 依次选取边构造最小生成树
    mst, count = [], 0
    for u, v, w in edges:
        if find(u) != find(v):
            mst.append((u, v, w))
            union(u, v)
            count += 1
            if count == n-1:
                break
    return mst

其中，edges是边的列表，每条边为一个三元组(u, v, w)，表示从节点u到节点v有一条权值为w的边；n为图的节点数。函数返回一个最小生成树的边的列表，每条边也是一个三元组。