Python:更改字典大小时发生Graph、DFS、set、defaultdict错误

Question

当我尝试用深度优先的方法打印断开连接的图形时，出现了这个问题。在

我使用defaultdict作为图的邻接列表表示。我知道如果一个键不在字典中，defaultdict会添加它并提供您设置的任何默认值（在我的例子中是list）。在

在您将其作为副本进行注释之前，我已经阅读了文章here和{a2}。它们显示在迭代过程中字典正在被更改，但我不太清楚在我的特定情况下是如何更改的。我没有从defaultdict弹出任何值。在

代码改编自GeeksForGeeks，但我决定对访问的顶点使用set而不是list，并将DFSUtil函数DFSHelper重命名。此外，正在打印的图形与下面的图相同，只是我添加了一个指向节点4的节点5。我试着加上这一点，使图真正断开。没有这个附加条目，就不会产生错误。

我的代码是：

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中的第一行从以下内容更改为：

^{pr2}$

到

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

错误会消失，但我不明白为什么会这样。我的假设是在defaultdict中搜索不是键的顶点4，并且由于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}

Answer 1

当您到达4和5的边缘时，当代码到达for neighbor in self.graph[vertex]时，您将遍历5的邻居。5的唯一邻居是4，然后以4作为顶点递归调用函数。在DFSHelper的下一次调用中，defaultdict为4添加了一个条目，因为它丢失了。在

只需在for循环之前添加条件if vertex in self.graph，以避免此错误。在