Что не так с обходом 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, но затем выдает ошибку «1013». Что не так с кодом и почему это происходит? Может кто-нибудь объяснить, пожалуйста

Примечание: Я искал на 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)