Python "list index out of range" 广度优先遍历错误

Question

我正在尝试在 python 中创建 BFS。虽然我的邻接表是正确的，但 Python 显示 "list index out of range" 错误，而且 BFS 答案并非始终正确。

下面是 python 代码，我添加了边，(1, 2), (2, 3) 和 (3, 3)

我正在尝试从顶点 2 找到 BFS，

from collections import defaultdict

# This class represents a directed graph using adjacency
# list representation
class Graph:

    # Constructor
    def __init__(self):

        # default dictionary to store graph
        self.graph = defaultdict(list)

    # function to add an edge to graph
    def addEdge(self,u,v):
        self.graph[u].append(v)

    # Function to print a BFS of graph
    def BFS(self, s):

        # Mark all the vertices as not visited
        visited = [False]*(len(self.graph))

        # Create a queue for BFS
        queue = []

        # Mark the source node as visited and enqueue it
        queue.append(s)
        visited[s] = True

        while queue:

            # Dequeue a vertex from queue and print it
            s = queue.pop(0)
            print s,

            # Get all adjacent vertices of the dequeued
            # vertex s. If a adjacent has not been visited,
            # then mark it visited and enqueue it
            for i in self.graph[s]:

                if visited[i] == False:

                    queue.append(i)
                    visited[i] = True




# Create a graph 
g = Graph()

g.addEdge(1, 2)
g.addEdge(2, 3)
g.addEdge(3, 3)

print "Following is Breadth First Traversal (starting from vertex 2)"
g.BFS(2)

它显示的错误；

Following is Breadth First Traversal (starting from vertex 2)
2
Traceback (most recent call last):
  File "test.py", line 58, in <module>
    g.BFS(2)
  File "test.py", line 42, in BFS
    if visited[i] == False:
IndexError: list index out of range

不确定，为什么显示超出范围。我已经将 vertex[1]、vertex[2] 和 vertex[3] 初始化为 False。此外，graph[1]、graph[2] 和 graph[3] 正在维护适当的邻接列表。

此外，BFS 答案应该是 2 3 但它只给出 2

Answer 1

visited 数组的长度为 3，因此 visited[3] 超出范围。

这个问题主要是因为 python 列表是从 0 开始索引的，因此行 visited = [False]*(len(self.graph)) 不会创建条目 visited[len(self.graph)].

此外，为了调试，我建议您在无法查看发生了什么的指令之前打印 i 和 visited 列表。

Answer 2

替换visited = [False]*(len(self.graph))
有了这个visited = [False]*(len(self.graph)+1)

Python "list index out of range" 广度优先遍历错误

Python "list index out of range" error in Breadth First Traversal

python

algorithm

breadth-first-search