Python中用defaultdict实现DFS遍历非连通图时的字典大小变更错误

我来帮你拆解这个问题的核心原因，以及为什么修改判断条件能解决问题：

错误的根本触发逻辑 #

我们一步步走一遍报错的流程：

1. 你添加了边5->4，此时你的defaultdict里的键是0,1,2,3,5（因为4没有作为起点被添加过边，所以不在字典里）。
2. DFS()方法开始遍历self.graph.keys()，当遍历到顶点5时，调用DFSHelper(5, visited)：
   • 5不在visited里，标记为已访问，然后遍历它的邻居4，调用DFSHelper(4, visited)。
3. 进入DFSHelper(4, visited)：
   • 4不在visited里，接下来执行for neighbor in self.graph[4]——这就是关键！因为defaultdict的特性，当你访问一个不存在的键时，它会自动把这个键添加到字典里（值为预设的空列表）。
   • 这时候self.graph的大小从5变成了6，而DFS()里的for vertex in self.graph.keys()还在迭代过程中，Python不允许在迭代字典视图（比如keys()）时修改字典的大小，所以直接抛出RuntimeError: dictionary changed size during iteration。

为什么修改判断条件能解决问题 #

你把判断条件改成if vertex not in visited and vertex in self.graph:后，当DFSHelper(4, visited)执行时：

• 首先检查vertex in self.graph，4此时不在字典里，条件不成立，跳过后续的循环逻辑，也就不会触发self.graph[4]的访问，自然不会让defaultdict自动添加新键，字典大小保持不变，迭代就能正常完成。

其他可选解决方案 #

除了添加vertex in self.graph的判断，还有两种常用的解决思路：

1. 迭代固定的键列表

在DFS()方法里，把self.graph.keys()转换成一个列表，这样迭代的是一个固定的快照，后续字典的变化不会影响迭代过程：

def DFS(self):
    visited = set()
    # 转换成列表，避免迭代时字典变化的问题
    for vertex in list(self.graph.keys()):
        if vertex not in visited:
            self.DFSHelper(vertex, visited)
    print('Visited : ', visited)

这样修改后，即使defaultdict自动添加了4这个键，迭代的还是初始的[0,1,2,3,5]列表，不会报错，同时4也会被正常访问到。

2. 改用普通字典

如果你不需要defaultdict自动添加键的特性，可以改用普通字典，在添加边时手动确保键存在：

class Graph:
    def __init__(self):
        self.graph = {}  # 普通字典
    def addEdge(self, u, v):
        if u not in self.graph:
            self.graph[u] = []
        self.graph[u].append(v)

这样访问不存在的键时会直接抛出KeyError，反而能帮你更早发现逻辑问题，避免意外修改字典结构。

验证对比 #

• 原错误输出：

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

• 修改判断条件后的输出：

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

• 改用list(self.graph.keys())后的输出（会访问到4）：

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

内容的提问来源于stack exchange，提问作者heretoinfinity