python - 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 是一个列表。但它的长度最多只能扩展到节点数。实际上......甚至不是这样，因为边缘是在当前实现中定向的。由于 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)