列表索引超出范围的错误对广度优先搜索功能

我创建一个广度优先搜索功能，将来自给定节点的网络中返回最短距离的阵列到所有节点，然后创建这些最短距离的矩阵所有节点。它适用于较小的网络，但当我尝试将其扩展到较大的网络时，出现列表索引超出范围的错误。列表索引超出范围的错误对广度优先搜索功能

我的功能

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。 –

列表索引超出范围的错误对广度优先搜索功能

回答

相关问题