Алгоритм Graph DFS с использованием python показывает индекс списка вне диапазона при доступе к списку утилит - PullRequest
Новая
       13

Алгоритм Graph DFS с использованием python показывает индекс списка вне диапазона при доступе к списку утилит

0 голосов
/ 08 февраля 2020

В данной программе я использовал стек для реализации DFS со списком утилит в качестве стека. Это итеративный подход. Ошибка здесь выглядит следующим образом:

---> 19 при посещении [i] == False:

IndexError: индекс списка вне диапазона 

    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_stack(self, start, visited):
            stack = []
            stack.append(start)

            while(len(stack) != 0):
               #pop
               i = stack.pop()

               #if not visited: visit and print
               if visited[i] == False: THE ERROR IS ON THIS LINE
                 visited[i]=True
                 print(i , end = " ")

               #push all unvisited adjacent vertices
               for adj in self.graph[i]:
                  if visited[i] == False:
                    stack.append(i)


       def DFS(self, start):
          visited = [False]*(len(self.graph)+1)
          self.dfs_stack(start,visited)



g = Graph()
g.addEdge(1, 2) 
g.addEdge(2, 3) 
g.addEdge(3, 4) 
g.addEdge(4, 5) 
g.addEdge(5, 1) 
g.addEdge(2, 6)
g.addEdge(3, 6)
g.addEdge(8, 7)
g.DFS(8)

1 Ответ

2 голосов
/ 08 февраля 2020

Длина вашего графика на самом деле составляет всего 6, поскольку ваш график: 

{1: [2], 2: [3, 6], 3: [4, 6], 4: [5], 5: [1], 8: [7]}

вы создали visited[], чтобы иметь длину 6, и когда вы получите доступ к visited[8], он выдаст IndexError: list index out of range.

Вам необходимо создать visited[] длиной, равной lastvertex т.е. 8

...