파이썬에서 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) 

내가 (무게, 첫 번째 노드, 두 번째 노드) 형식으로 "가장자리"를 변경하면, 내가 할 수있는 (무게의 형식으로 정답을 가지고, 첫 번째 노드 그 , 제 2 노드). 하지만 "가장자리"를 (첫 번째 노드, 두 번째 노드, weigth) 형식으로 사용하려면 어떻게 수정해야합니까?

Answer 1

언뜻보기에,이 시도 :

edges = list(graph['edges']) 

대신

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