DFS 遍历有什么问题?

Question

我已经为下图尝试了这个DFS代码

2___3___4___5
1 ___/
10___11___12__13

这是代码：

from collections import defaultdict
class Graph:
def __init__(self):
self.graph = defaultdict(list)
def addEdge(self,u,v):
self.graph[u].append(v)
def DFS_traversal(self,node,visited):
visited[node] = True
print(node)
for neighbour in self.graph[node]:
if visited[neighbour] == False:
self.DFS_traversal(neighbour,visited)
def DFS(self,start_node):
visited = [False]*len(self.graph)
print(self.graph)
self.DFS_traversal(start_node,visited)

g1 = Graph()
g1.addEdge(1,2)
g1.addEdge(2,3)
g1.addEdge(3,4)
g1.addEdge(4,5)
g1.addEdge(1,10)
g1.addEdge(10,11)
g1.addEdge(11,12)
g1.addEdge(12,13)
g1.DFS(1)

最后，当我执行此代码时，我遇到了一个错误。它从 1 打印到 5，但随后，它给出一个错误，说IndexError: list index out of range.代码有什么问题，为什么会发生这种情况？有人可以解释一下吗

注意：我在SO上搜索了，但是，我似乎没有找到解决此问题的方法。

Answer 1

visited是一个列表。但它的长度只能延伸到节点的数量。实际上。。。甚至不是这样，因为 Edge 在当前实现中是定向的。由于len(self.graph)是 7(键为 1、2、3、4、10、11、12)，因此访问visited[10]会引发索引错误，这是应该的。6是可以访问的最大索引。

而不是

visited = [False]*len(self.graph)

使用字典，因为您的节点不是顺序的。

visited = {node: False for node in self.graph}

我还会在addEdge方法中添加一条线，将边建模为无向：

self.graph[v].append(u)