Prim算法 回溯 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))

邻接列表如下：

^{pr2}$

在到达第6个顶点（空集合）之前，输出是正确的：

^{3}$

由于我对下一个顶点的定义，索引超出范围：

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

不幸的是，我不确定如何从这里回到第五个节点，然后再回到第四个节点。在

谢谢你的帮助

Answer 1

看看这里，他们似乎在这里讨论得很好：） http://learn.canterbury.ac.nz/mod/forum/view.php?id=377078