在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) 

我发现，如果我变“边缘”到（重量，第一点，第二点）格式，我可以得到的（重量格式正确答案，第一个节点，第二个节点）。但是如果我想以（第一个节点，第二个节点，weigth）的格式使用“Edges”，我该如何修改它？

Answer 1

乍一看，试试这个：

edges = list(graph['edges']) 

代替

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