在 Python 中实施 Kruskal 算法时输出错误

Question

我正在研究 Krusal 的算法。但是我没有得到正确的输出。我不知道我哪里弄错了

这是我的代码：

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(graph):
    for vertice in graph['vertices']:
        make_set(vertice)

    minimum_spanning_tree = set()
    edges = list(graph['edges'])

    for edge in edges:
        vertice1, vertice2, weight = edge
        if find(vertice1) != find(vertice2):
            union(vertice1, vertice2)
            minimum_spanning_tree.add(edge)
    return minimum_spanning_tree






graph = {
    'vertices': [0,1, 2, 3, 4, 5],
    'edges': set([     //(first node, second node, weight)
        (0, 3,5),
        (3, 5,2),
        ( 5, 4,10),
        ( 4, 1,3),
        (1, 0,8),
        (0, 2,1),(2,3,6),( 2,5,4),( 2,4,9),(2,1,7),
        ])
    }

a = kruskal(graph)

print(a)

我发现如果我把"Edges"改成（权重，第一个节点，第二个节点）格式，我可以得到（权重，第一个节点，第二个节点）格式的正确答案。但是，如果我想以（第一个节点，第二个节点，权重）的格式使用 "Edges"，我该如何修改它？

Answer 1

乍一看，试试这个：

edges = list(graph['edges'])

改为

edges = sorted(graph['edges'], key=lambda e: e[2])

在 Python 中实施 Kruskal 算法时输出错误

Wrong output in Implementing Kruskal Algorithm in Python

python

graph-theory

minimum-spanning-tree

kruskals-algorithm