Kurskal算法求最小生成树python具体实例

Kruskal算法是一种用于计算最小生成树的贪心算法。下面是一个基于Python的Kruskal算法实现的具体例子：

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

# 定义一个辅助函数，用于合并两个集合
def union(parents, ranks, x, y):
    xroot = find(parents, x)
    yroot = find(parents, y)

    if ranks[xroot] < ranks[yroot]:
        parents[xroot] = yroot
    elif ranks[xroot] > ranks[yroot]:
        parents[yroot] = xroot
    else:
        parents[yroot] = xroot
        ranks[xroot] += 1

# 定义Kruskal算法函数
def kruskal(graph, V):
    result = []
    i = 0
    e = 0

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

    parents = []
    ranks = []
    for node in range(V):
        parents.append(node)
        ranks.append(0)

    # 对所有边进行遍历
    while e < V - 1:
        u, v, w = graph[i]
        i = i + 1
        x = find(parents, u)
        y = find(parents, v)

        # 如果加入这条边不会形成环，则把它加入结果集合
        if x != y:
            e = e + 1
            result.append([u, v, w])
            union(parents, ranks, x, y)

    return result

# 测试
graph = [[0, 1, 10], [0, 2, 6], [0, 3, 5], [1, 3, 15], [2, 3, 4]]
V = 4
result = kruskal(graph, V)
print("最小生成树：")
for u, v, weight in result:
    print("%d - %d: %d" % (u, v, weight)))

输出结果为：

最小生成树：
2 - 3: 4
0 - 3: 5
0 - 1: 10

其中，graph是一个由三元组组成的列表，每个三元组表示一条边的起点、终点和权重。V是图的顶点数。kruskal函数返回一个由三元组组成的列表，表示最小生成树的所有边。