kruskal算法的python代码

下面是Kruskal算法的Python代码实现，假设我们已经有一个表示图的邻接矩阵G和边的列表edges，列表中每个元素为(u, v, w)，表示一条边连接了u和v，权重为w。

def kruskal(G, edges):
    # 初始化并查集
    parent = [-1] * len(G)
    rank = [0] * len(G)

    # 定义查找根节点的函数
    def find_root(x):
        if parent[x] == -1:
            return x
        else:
            root = find_root(parent[x])
            parent[x] = root
            return root

    # 定义合并集合的函数
    def union(x, y):
        root_x, root_y = find_root(x), find_root(y)
        if root_x == root_y:
            return False
        else:
            if rank[root_x] < rank[root_y]:
                parent[root_x] = root_y
            elif rank[root_x] > rank[root_y]:
                parent[root_y] = root_x
            else:
                parent[root_y] = root_x
                rank[root_x] += 1
            return True

    # 将边按照权重从小到大排序
    edges.sort(key=lambda x: x[2])

    # 遍历每条边，加入最小生成树的边集合中
    mst = []
    for edge in edges:
        u, v, w = edge
        if union(u, v):
            mst.append(edge)

    return mst

代码中使用了并查集来判断加入一条边是否会形成环，并按照边权从小到大排序来遍历所有边。最终返回的是最小生成树的边集合。