我上面有這段代碼：
N = 8
inf = 99
graph = [[0,0,6,7,0,8,0,0], #1
[0,0,0,3,4,2,0,0], #2
[6,0,0,0,0,3,0,7], #3
[7,3,0,0,9,0,0,0], #4
[0,4,0,9,0,0,5,0], #5
[8,2,3,0,0,0,9,3], #6
[0,0,0,0,5,9,0,0], #7
[0,0,7,0,0,3,0,0]] #8
# Матрица инцидентности для остовного дерева (задаётся пустой)
spanning_tree_graph = [[0,0,0,0,0,0,0,0] for node in range(N)]
selected_nodes = [False for node in range(N)] # какие вершины включены, какие нет
while(False in selected_nodes): # Пока есть невключенные вершины:
minimum = inf
start = 0
end = 0
for i in range(0, N):
if selected_nodes[i]:
for j in range(0 i, N):
if(not selected_nodes[j] and graph[i][j] > 0):
if graph[i][j] < minimum:
minimum = graph[i][j]
start, end = i, j
selected_nodes[end] = True
spanning_tree_graph[start][end] = minimum
if minimum == inf:
spanning_tree_graph[start][end] = 0
spanning_tree_graph[end][start] = spanning_tree_graph[start][end]
print(spanning_tree_graph)
但是輸出是空的，我不知道為什么。
我正在嘗試渲染排序圖。像這樣
[[0, 8, 2, 4, 0, 0, 0, 0], [8, 0, 0, 0, 0, 0, 0, 0], [2, 0, 0, 0, 0, 5, 0, 4], [4, 0, 0, 0, 1, 0, 0, 0], [0, 0, 0, 1, 0, 0, 4, 0], [0, 0, 5, 0, 0, 0, 0, 0], [0, 0, 0, 0, 4, 0, 0, 0], [0, 0, 4, 0, 0, 0, 0, 0]]
uj5u.com熱心網友回復：
這是我認為是固定的實作。
N = 8
inf = 99
graph = [[0,0,6,7,0,8,0,0], #1
[0,0,0,3,4,2,0,0], #2
[6,0,0,0,0,3,0,7], #3
[7,3,0,0,9,0,0,0], #4
[0,4,0,9,0,0,5,0], #5
[8,2,3,0,0,0,9,3], #6
[0,0,0,0,5,9,0,0], #7
[0,0,7,0,0,3,0,0]] #8
# Матрица инцидентности для остовного дерева (задаётся пустой)
spanning_tree_graph = [[0,0,0,0,0,0,0,0] for node in range(N)]
selected_nodes = [False for node in range(N)] # какие вершины включены, какие нет
selected_nodes[0] = True
while(False in selected_nodes): # Пока есть невключенные вершины:
minimum = inf
start = 0
end = 0
for i in range(0, N):
if selected_nodes[i]:
for j in range(0, N):
if(not selected_nodes[j] and graph[i][j] > 0):
if graph[i][j] < minimum:
minimum = graph[i][j]
start, end = i, j
selected_nodes[end] = True
spanning_tree_graph[start][end] = minimum
if minimum == inf:
spanning_tree_graph[start][end] = 0
break
spanning_tree_graph[end][start] = spanning_tree_graph[start][end]
for g in spanning_tree_graph:
print(g)
這是我修復的錯誤。
- 您必須從生成樹圖中的一個節點（任何節點）開始，它才能開始。
- 您正在遍歷對以找到
i選定的節點而j不是。你不愿意考慮j < i，但它可能是。 - 如果
minimum == inf那么下一次回圈迭代會發現相同的，并且您有一個無限回圈。所以break用偏樹。 - 我修改了
print最后的以更方便的格式顯示。
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/490964.html
上一篇：找到這個回圈的時間復雜度？
下一篇：計算集差的最有效演算法？