列表索引超出範圍的錯誤對廣度優先搜索功能

我創建一個廣度優先搜索功能，將來自給定節點的網絡中返回最短距離的陣列到所有節點，然後創建這些最短距離的矩陣所有節點。它適用於較小的網絡，但當我嘗試將其擴展到較大的網絡時，出現列表索引超出範圍的錯誤。列表索引超出範圍的錯誤對廣度優先搜索功能

我的功能

def bfs_short(G,node): 
    queue=[] 
    visit=[] 
    parent=[] 
    for n in range(len(G)): 
     visit.append(False) 
     parent.append(None) 
    queue.append(node) 
    visit[node]=True 
    while len(queue)!=0: 
     current=queue.pop(0) 
     for a in G[current]: 
      if visit[a]==False: 
       visit[a]=True 
       parent[a]=current 
       queue.append(a) 
    distances=[] 
    for n in range(len(G)): 
     distances.append(0) 
    for n in range(len(G)): 
     dist=0 
     current=n 
     while parent[current]!=None: 
      dist=dist+1 
      current=parent[current] 
     distances[n]=dist 
    return distances 

    V=len(G.keys()) 
    dist_matrix=np.empty([V, V]) 
    keys = G.keys() 
    for k in keys: 
     dist_matrix[k,:]=bfs_short(G,k) 
    return dist_matrix

的錯誤是：

<ipython-input-296-b89665c85020> in bfs_short(G, node) 
    11   current=queue.pop(0) 
    12   for a in G[current]: 
---> 13    if visit[a]==False: 
    14     visit[a]=True 
    15     parent[a]=current 

IndexError: list index out of range

它正常工作與這個小小的adjaceny矩陣

G_dict2 = {0:[1,3], 1:[0,2,5], 2:[1,3], 3:[0,2], 4:[1,2,3], 5:[0,4], 6:[3,4]}

但它給人的錯誤使用更大時網絡。網絡太大（約2,000個節點）實際上粘貼在這裏，但我不確定一個小節選是否有助於說明任何內容。

network= {0: [1, 2], 
1: [6, 0, 7], 
2: [8, 9, 10], 
3: [4, 1, 5], 
4: [11, 12, 13], 
5: [14, 15, 16], 
6: [17, 1, 18], 
7: [19, 20, 1], 
8: [21, 2, 3], 
9: [2, 22, 23], 
10: [24, 2, 25], 
11: [4], 
12: [4, 13, 26], 
13: [12, 4, 27], 
14: [28, 29, 30], 
15: [31, 5, 32], 
16: [33, 5], 
17: [6, 34, 35], 
18: [36, 37, 38], 
19: [7, 39, 40], 
20: [41, 7, 42],}

有沒有人注意到會導致它在更大的網絡上發生此錯誤的功能的任何明顯？

謝謝！

來源

2017-04-16 yogz123

這不是一個numpy的問題初始化訪問解決這個問題;它只是列表索引。來自'G [當前]'的'a'超越列表'訪問'大小。 'visit'用'append'擴展。您只需要輸入一些診斷打印來跟蹤列表大小，並檢測爲什麼它不如您認爲的那樣大，或者爲什麼'G'的值太大。 – hpaulj

IE，錯誤行之前，添加像'打印（目前，G（當前），LEN（G），一，LEN（訪問））' –

你的第一個循環創建一個'visit'陣列久，是因爲作爲'g^'。但它看起來像「訪問[a]」正在使用其中一個子列表中的數字進行索引。以你的例子'visit'爲20長，但'network [7] [1]'爲20。'visit [20]'會引發這個錯誤。 – hpaulj

正如我讀取代碼，該錯誤僅當不存在與（G_dict2）大於或等於爲len的值鄰接矩陣中的節點發生。

這種情況很容易發生無論是否有在鄰接表比在G_dict2，例如最大的關鍵大的節點如果網絡中最大的節點是2017年，但有一個列表21: [2018]，或鄰接矩陣已經缺少的節點，即對於一些節點其中i < LEN（G_dict2），在這種情況下，參觀了長度將太沒有進入最大可能節點值的縮寫。您可以通過以下測試：

from itertools import chain 
assert max(chain(*G_dict2.values())) < len(G_dict2), "You got an out of range because G_dict2 has a node with id {} which is larger than the range of visit (0, {})".format(max(chain(*G_dict2.values())), len(G_dict2) - 1) 
assert max(G_dict2.keys()) < len(G_dict2), "You got an out of range because visit is constructed by iterating over the *number* of keys in the dict, but the node {} is not in the range (0, len(G_dict2)-1) = (0, {})".format(max(G_dict2.keys()), len(G_dict2)-1)

您可以通過基於所有鄰接表的最大值，例如：

from itertools import chain 
visit = [False]*(max(chain.from_iterable(G.values()))+1) 
parent = [None]*(max(chain.from_iterable(G.values()))+1)

來源

2017-04-16 18:31:20

它並不直接回答問題，但我也應該指出這並不是產生全部最短路徑的最有效方式，這是在函數結束時出現的情況。您可能想查看https://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm。 –

列表索引超出範圍的錯誤對廣度優先搜索功能

回答

相關問題