Python: Graph, DFS, set, defaultdict - ошибка при изменении размера словаря - PullRequest
Новая
       18

Python: Graph, DFS, set, defaultdict - ошибка при изменении размера словаря

0 голосов
/ 30 мая 2018

Эта проблема возникла, когда я пытался с помощью глубокой печати распечатать отключенный граф.

Я использую defaultdict для представления графа в списке смежности.Я знаю, что если ключа нет в словаре, defaultdict добавит его и предоставит любое значение по умолчанию (в моем случае list).

Прежде чем комментировать это как дубликатЯ прочитал сообщения здесь и здесь .Они показывают, что словарь изменяется во время итерации, но я не совсем понимаю, как в моем конкретном случае.Я не выскакиваю какие-либо значения из defaultdict.

Код адаптирован из GeeksForGeeks , но я решил использовать set вместо list для посещенных вершин, и я переименовал функцию DFSUtil, DFSHelper.Более того, печатаемый график такой же, как и приведенный ниже, за исключением того, что я добавил узел 5, указывающий на узел 4. Я попытался добавить это, чтобы сделать график действительно отключенным.Без этой дополнительной записи ошибка не выдается.GeeksForGeeks graph being printed

Вот мой код: 

from collections import defaultdict

class Graph:
  def __init__(self):
    self.graph = defaultdict(list)

  def addEdge(self, u, v):
    self.graph[u].append(v)

  def DFSHelper(self, vertex, visited):
    # recursively visit adjacent nodes
    if vertex not in visited:# and vertex in self.graph:
      visited.add(vertex)
      print(vertex)

      for neighbor in self.graph[vertex]:
        self.DFSHelper(neighbor, visited)

  def DFS(self): # for disconnected graph
    visited = set()

    # print(self.graph.keys())
    for vertex in self.graph.keys():
      if vertex not in visited:
        self.DFSHelper(vertex, visited)

    print('Visited : ', visited)

g = Graph()
g.addEdge(0, 1)
g.addEdge(0, 2)
g.addEdge(1, 2)
g.addEdge(2, 0)
g.addEdge(2, 3)
g.addEdge(3, 3)
g.addEdge(5, 4) # disconnected graph - I added this edge myself

print(g.graph)
print("Following is DFS of a disconnected graph")
g.DFS()

Я заметил, что когда я изменил первую строку в DFSHelper с: 

if vertex not in visited:

до 

if vertex not in visited and vertex in self.graph:

ошибка исчезнет, ​​но я не понимаю, почему это так.Я предполагаю, что вершина 4, которая не является ключом, ищется в defaultdict, и поскольку действие по умолчанию defaultdict заключается в создании записи, а не в возврате ключевой ошибки, defaultdict изменяется во время итерации.Однако я не вижу, как 4 передается в функцию defaultdict.

Вот вывод с ошибкой.

Following is DFS of a disconnected graph
0
1
2
3
5
4
Traceback (most recent call last):
  File "depth-first-search-disconnected_graph.py", line 41, in <module>
    g.DFS()
  File "depth-first-search-disconnected_graph.py", line 25, in DFS
    for vertex in self.graph.keys():
RuntimeError: dictionary changed size during iteration

Обратите внимание на печать 4.

Вот вывод с исправленной ошибкой.

Following is DFS of a disconnected graph
0
1
2
3
5
Visited :  {0, 1, 2, 3, 5}

1 Ответ

0 голосов
/ 31 мая 2018

Когда вы добираетесь до границ 4 и 5, вы проходите через соседей 5, когда код достигает for neighbor in self.graph[vertex].Единственный сосед 5 равен 4, и затем вы вызываете функцию рекурсивно с 4 в качестве вершины.В следующем вызове DFSHelper defaultdict добавляет запись для 4, потому что она отсутствует.

Просто добавьте ваше условие if vertex in self.graph перед циклом for, чтобы избежать этой ошибки.

...