使用collections.defaultdict迭代字典时出现RuntimeError: dictionary changed size during iteration的原因排查

嘿，我一眼就看出问题出在哪了——你用的是collections.defaultdict，而它的「自动添加不存在的键」特性正好在你的DFS过程中偷偷修改了字典的大小，导致遍历的时候报错。

问题根源 #

你在_dfs函数里写了for e in graph[i]，当i是一个原本不在graph里的课程编号时，defaultdict会自动把这个i作为键添加到字典中，并且赋值为空列表[]。

拿你的测试用例canFinish(3, [[0,1],[0,2],[1,2]])来说：

1. 初始构建的graph是{0: [1,2], 1: [2]}
2. 当你开始遍历graph时，第一个遍历到的键是0，进入_dfs(0)
3. 接着处理graph[0]里的1，进入_dfs(1)
4. 然后处理graph[1]里的2，进入_dfs(2)
5. 这时候graph[2]不存在，defaultdict会自动给graph新增键2，值为[]——这就导致字典的size从2变成了3
6. 而此时你还在遍历原始的graph迭代器，迭代器发现字典大小变化，直接抛出RuntimeError

你的测试代码之所以没问题，是因为你在遍历之前就已经访问了a[2]，字典在遍历前就已经确定了大小，遍历过程中没有新增键，所以不会报错。

解决方案 #

有几种简单的修复方式，选一种适合你的就行：

1. 遍历前把字典的键转成固定列表

把遍历的代码改成：

for i in list(graph):
    if not _dfs(i):
        return False

这样遍历的是graph在遍历开始时的键的副本，就算后面字典新增了键，也不会影响当前的遍历过程。

2. 避免defaultdict自动新增键

在DFS里访问graph时，用get方法获取值，如果键不存在就返回空列表，这样就不会触发defaultdict的自动添加：

def _dfs(i):
    if i in visited:
        return False
    visited.add(i)
    # 用get方法，不存在则返回空列表，不会新增键
    for e in graph.get(i, []):
        if not _dfs(e):
            return False
    visited.remove(i)
    return True

3. 把defaultdict转成普通字典

构建完graph后，把它转成普通字典，这样访问不存在的键会抛出KeyError，但结合get方法就没问题：

graph = collections.defaultdict(list)
for i in prerequisites:
    graph[i[0]].append(i[1])
# 转成普通字典
graph = dict(graph)

修改后的完整代码示例 #

这里用第一种方案修改后的代码：

import collections

def canFinish(numCourses: int, prerequisites:[[]]) -> bool:
    graph = collections.defaultdict(list)
    visited = set()
    for i in prerequisites:
        graph[i[0]].append(i[1])
    def _dfs(i):
        if i in visited:
            return False
        visited.add(i)
        for e in graph[i]:
            if not _dfs(e):
                return False
        visited.remove(i)
        return True
    # 遍历graph键的列表副本
    for i in list(graph):
        if not _dfs(i):
            return False
    return True

测试一下你的用例canFinish(3, [[0,1],[0,2],[1,2]])，现在应该能正常返回True了。

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