时间戳

首页 > 解决方案 > DFS遍历有什么问题？

python - DFS遍历有什么问题？

问题描述

我已经为下图尝试了这个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 上进行了搜索，但是，我似乎没有找到解决此问题的方法。

标签： pythonpython-3.xalgorithmdepth-first-search

解决方案

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)

推荐阅读