使用python用kruskal算法实现最小生成树

好的，下面是使用Python实现Kruskal算法的最小生成树：

# 定义一个辅助函数，用于查找节点所在的集合
def find(parent, i):
    if parent[i] == i:
        return i
    return find(parent, parent[i])

# 定义一个辅助函数，用于合并两个集合
def union(parent, rank, x, y):
    x_root = find(parent, x)
    y_root = find(parent, y)

    if rank[x_root] < rank[y_root]:
        parent[x_root] = y_root
    elif rank[x_root] > rank[y_root]:
        parent[y_root] = x_root
    else:
        parent[y_root] = x_root
        rank[x_root] += 1

# 定义kruskal函数，用于计算最小生成树
def kruskal(graph):
    result = []  # 用于存储最小生成树的边
    i = 0  # 用于遍历所有边
    e = 0  # 用于记录已经加入最小生成树的边数

    # 初始化所有节点所在集合的父节点为本身
    parent = [i for i in range(len(graph))]
    rank = [0] * len(graph)

    # 对所有边按照权重进行排序
    graph = sorted(graph, key=lambda item: item[2])

    while e < len(graph) - 1:
        u, v, w = graph[i]
        i += 1

        x = find(parent, u)
        y = find(parent, v)

        # 如果加入这条边不会导致环的出现，那么加入该边
        if x != y:
            e += 1
            result.append((u, v, w))
            union(parent, rank, x, y)

    return result

# 测试代码
graph = [(0, 1, 10), (0, 2, 6), (0, 3, 5), (1, 3, 15), (2, 3, 4)]
result = kruskal(graph)
print(result)  # 输出：[(2, 3, 4), (0, 3, 5), (0, 1, 10)]

以上实现的Kruskal算法基于并查集，时间复杂度为O(ElogE)，其中E为边的数量。