Python的「列表索引超出範圍」廣度優先遍歷中的錯誤

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列表之前的指令，看不清是怎麼回事。