python - Python:Graph、DFS、set、defaultdict - 更改字典大小时出错
问题描述
当我尝试使用深度优先的方法打印断开连接的图时,就会出现这个问题。
我正在使用defaultdict
图形的邻接列表表示形式。我知道,如果一个键不在字典中,defaultdict
则将添加它并提供您设置的任何默认值(在我的情况下为 a list
)。
在您将此评论为重复之前,我已阅读此处和此处的帖子。他们表明在迭代过程中字典正在被更改,但在我的特定情况下我不太明白。我没有从defaultdict
.
该代码改编自GeeksForGeeks但我决定使用 aset
而不是 alist
来访问访问的顶点,并将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 中的第一行更改为:
if vertex not in visited:
到
if vertex not in visited and vertex in self.graph:
错误会消失,但我不明白为什么会这样。我的假设是正在搜索不是键的顶点 4,defaultdict
并且由于 a 的默认操作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}
解决方案
当你到达 4 和 5 的边缘时,当代码到达 5 时,你会穿过 5 的邻居for neighbor in self.graph[vertex]
。5 的唯一邻居是 4,然后您以 4 作为顶点递归调用该函数。在 的下一次调用中DFSHelper
,defaultdict 添加了 4 的条目,因为它丢失了。
只需在 for 循环之前添加您的条件if vertex in self.graph
即可避免此错误。
推荐阅读
- r - R Shiny:用户更改输入后更新数据框
- python - 如何在不同范围之间的熊猫数据框中的列上应用多个规范化
- r - 如何使用具有已知日期格式的因子级别来通知我的数据框的其余部分?
- rust - 如何在关联类型上定义特征界限?
- airflow - 触发的 DAG 无法从 TriggerDagRunOperator 获取参数
- php - PHP - 未跳过标头时,导出 CSV 函数不处理所有数据
- php - 如何替换array_value?
- c# - PHP 函数分解为 C# 以在开始和结束之间获取值
- javascript - 无法使用 fetch api 发布 wordpress
- vb.net - 将动态选项卡中的数据表添加到数组列表中