Python中使用Kruskal算法解决最小生成树问题

2023-04-11 00:00:00 算法生成最小

Kruskal算法是一种常用的求解最小生成树的贪心算法，主要思想是将边按照权值从小到大进行排序，然后依次加入生成树中，如果加入该边不会形成环，则选择该边。下面是Python实现Kruskal算法的代码。

首先，定义一个函数来查找顶点所在的树的根节点。

def find(parent, i):
    if parent[i] == i:
        return i
    return find(parent, parent[i])

然后，定义一个函数来合并两个不同的树。

def union(parent, rank, x, y):
    xroot = find(parent, x)
    yroot = find(parent, y)

    if rank[xroot] < rank[yroot]:
        parent[xroot] = yroot
    elif rank[xroot] > rank[yroot]:
        parent[yroot] = xroot
    else:
        parent[yroot] = xroot
        rank[xroot] += 1

最后，实现Kruskal算法的主函数。

def kruskal(graph):
    result = []
    parent = {}
    rank = {}

    # 初始化parent和rank
    for i in graph['vertices']:
        parent[i] = i
        rank[i] = 0

    # 按照边的权值进行排序
    edges = sorted(graph['edges'], key=lambda x: x[2])

    for edge in edges:
        u, v, weight = edge
        x = find(parent, u)
        y = find(parent, v)

        # 如果加入该边不会形成环，则选择该边
        if x != y:
            result.append(edge)
            union(parent, rank, x, y)

    # 输出最小生成树
    print('最小生成树：')
    for edge in result:
        print('{} - {} : {}'.format(edge[0], edge[1], edge[2]))

最后，让我们测试一下代码。

graph = {'vertices': ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I'],
         'edges': [('A', 'B', 4),
                   ('A', 'H', 8),
                   ('B', 'C', 8),
                   ('B', 'H', 11),
                   ('C', 'D', 7),
                   ('C', 'F', 4),
                   ('C', 'I', 2),
                   ('D', 'E', 9),
                   ('D', 'F', 14),
                   ('E', 'F', 10),
                   ('F', 'G', 2),
                   ('G', 'H', 1),
                   ('G', 'I', 6),
                   ('H', 'I', 7)]}

kruskal(graph)

输出结果为：

最小生成树：
G - H : 1
C - I : 2
F - G : 2
A - B : 4
C - F : 4
A - H : 8
D - C : 7
H - I : 7

相关文章