0
私は隣接リストを取り、プリムのパスを生成するプログラムを書いていますが、アルゴリズムをバックトラックするのに問題があります。プリムのアルゴリズムバックトラッキングPython
コード：
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番目に追跡する方法が不明です。あなたの援助
任意のヘルプ？....... –
バンプ....... ......... –