Prim의 알고리즘 Back tracking Python

Question

인접 목록을 사용하여 Prim의 경로를 생성하는 프로그램을 작성하고 있지만 알고리즘을 역 추적하는 데 문제가 있습니다.

번호 :

def lowest_cost(conduits_info_str): 
    graph = conduits_info_str.splitlines() 
    num_vertices = int(graph[0].split()[1]) 
    graph = graph[1:] 
    adj_list = adjacency_list(conduits_info_str) 
    num_edges = len(adj_list) 
    visited = [] 
    cost = 0 
    if num_edges > 0: 
     visited.append(int(graph[0].split()[0])) 
    print(adj_list) 
    while len(visited) < len(adj_list): 
     print("Next Node: ",visited[-1]) 
     minimum = adj_list[visited[-1]][0][1] 
     min_vertex = adj_list[visited[-1]][0][0] 
     for each in adj_list[visited[-1]]: 
      if each[1] < minimum and each[0] not in visited: 
       min_vertex = each[0] 
       minimum = each[1] 
      visited.append(min_vertex) 

    return adj_list 





def adjacency_list(graph_str): 
    is_weighted = False 
    is_directed = False 
    graph_list = graph_str.splitlines() 
    num_verticies = int(graph_list[0].split()[1]) 
    graph_list.pop(0) 
    adj_list = [[] for _ in range(num_verticies)] 

    if 'D' in graph_str: 
     is_directed = True 
    if 'W' in graph_str: 
     is_weighted = True 


    if is_weighted == True: 
     for line in graph_list: 
      line_list = line.split() 
      a = int(line_list[0]) 
      b = int(line_list[1]) 
      c = int(line_list[2]) 
      adj_list[int(a)].append((b,c)) 
    else: 
     for line in graph_list: 
      line_list = line.split() 
      i = int(line_list[0]) 
      j = int(line_list[1]) 
      if not is_directed: 
       adj_list[j].append((i, None))    
      adj_list[int(i)].append((j, None)) 
    return adj_list 


conduits_info = """\ 
U 7 W 
0 1 5 
0 2 7 
0 3 12 
1 2 9 
2 3 4 
1 4 7 
2 4 4 
2 5 3 
3 5 7 
4 5 2 
4 6 5 
5 6 2 
""" 

print(lowest_cost(conduits_info)) 

인접성리스트는 다음과 같다 :

[[(1, 5), (2, 7), (3, 12)], [(2, 9), (4, 7)], [(3, 4), (4, 4), (5, 3)],[(5, 7)], [(5, 2), (6, 5)], [(6, 2)], []] 

는 6 정점 (공집합)에 도달 할 때까지 출력 올 :

visited_list = [0, 1, 4, 5] 

을 다음 정점의 정의로 인해 범위를 벗어납니다 :

minimum = adj_list[visited[-1]][0][1] 
    min_vertex = adj_list[visited[-1]][0][0] 

불행히도 여기에서 5 번째 노드까지 추적하고 4 번째로 추적하는 방법을 확신 할 수 없습니다. 당신의 도움

Answer 1

에 대한

덕분에 그들이 좋은 여기 토론 : http://learn.canterbury.ac.nz/mod/forum/view.php?id=377078