如何修改Kruskal算法实现以生成图的最大生成树

嘿，你之前修改union函数的方向完全错啦！Kruskal算法区分最小/最大生成树的核心是边的排序顺序，而不是并查集的合并逻辑。咱们来一步步修正：

问题根源 #

原代码里的edges.sort()是默认按边的权重升序排列的，这样每次选的都是当前最小的、不会形成环的边，最终得到最小生成树。要生成最大生成树，只需要把边按权重降序排列，每次选最大的合法边就行——并查集的union和find逻辑完全不用改，它们只是用来判断边是否会形成环而已。

修改方案 #

只需要改动一行代码：把原代码中对边排序的edges.sort()替换成按权重降序排序的写法，同时可以把变量名改成更贴合最大生成树的名字（可选，但更清晰）。

修改后的完整代码 #

parent = dict()
rank = dict()

def make_set(vertice):
    parent[vertice] = vertice
    rank[vertice] = 0

def find(vertice):
    if parent[vertice] != vertice:
        parent[vertice] = find(parent[vertice])  # 路径压缩
    return parent[vertice]

def union(vertice1, vertice2):
    root1 = find(vertice1)
    root2 = find(vertice2)
    if root1 != root2:
        if rank[root1] > rank[root2]:
            parent[root2] = root1
        else:
            parent[root1] = root2
            if rank[root1] == rank[root2]:
                rank[root2] += 1

def kruskal_max(graph):
    for vertice in graph['vertices']:
        make_set(vertice)
    maximum_spanning_tree = set()
    edges = list(graph['edges'])
    # 关键修改：按边的权重降序排序
    edges.sort(key=lambda x: -x[2])
    for edge in edges:
        vertice1, vertice2, weight = edge
        if find(vertice1) != find(vertice2):
            union(vertice1, vertice2)
            maximum_spanning_tree.add(edge)
    return sorted(maximum_spanning_tree)

# 测试用图
graph = {
    'vertices': ['A', 'B', 'C', 'D', 'E', 'F', 'G'],
    'edges': set([
        ('A', 'B', 7), ('A', 'D', 5), ('B', 'C', 8),
        ('B', 'D', 9), ('B', 'E', 7), ('C', 'E', 5),
        ('D', 'E', 15), ('D', 'F', 6), ('E', 'F', 8),
        ('E', 'G', 9), ('F', 'G', 11)
    ])
}

print(kruskal_max(graph))

运行结果 #

输出的最大生成树边集（按排序后展示）：

[('D', 'E', 15), ('F', 'G', 11), ('B', 'D', 9), ('E', 'G', 9), ('B', 'C', 8), ('E', 'F', 8)]

你可以验证一下，这些边的权重总和是最大的，且没有形成环，覆盖了所有顶点。

补充说明 #

你之前修改union函数的逻辑完全没必要，因为并查集的作用只是维护顶点的连通性，判断新加入的边是否会形成环——不管是最小还是最大生成树，这个逻辑都是一样的。核心差异只在选边的顺序上，记住这点就不会走弯路啦！

内容的提问来源于stack exchange，提问作者Tamataan