我得到了“RuntimeError:dictionary在迭代期间更改了大小”，尽管没有对dictionary进行任何更改。我如何解决这个问题？

Question

我试图在Python 3.7中实现拓扑排序，但收到以下错误消息：

Traceback (most recent call last):
  File "D:/pythonchallenge/topological_sort.py", line 42, in <module>
    graph_.Topological_Sort()
  File "D:/pythonchallenge/topological_sort.py", line 28, in Topological_Sort
    for node in self.adj_list:
RuntimeError: dictionary changed size during iteration

这是我的密码：

# Topological Sort
# Algorithm - https://www.geeksforgeeks.org/topological-sorting/

from collections import defaultdict


class Graph:
    def __init__(self, size):
        self.adj_list = defaultdict(list)
        self.visited = []
        self.size = size

    def Insert_Node(self, u, v):
        self.adj_list[u].append(v)

    def Topological_Sort_Util(self, input_node, input_stack):
        self.visited[input_node] = True

        for child in self.adj_list[input_node]:
            if not self.visited[child]:
                self.Topological_Sort_Util(child, input_stack)

        input_stack.append(input_node)

    def Topological_Sort(self):
        self.visited = [False] * self.size
        stack_ = []
        for node in self.adj_list:
            if not self.visited[node]:
                self.Topological_Sort_Util(node, stack_)

        while len(stack_) != 0:
            print(stack_.pop(-1), end=" ")


if __name__ == '__main__':
    graph_ = Graph(4)
    graph_.Insert_Node(1, 3)
    graph_.Insert_Node(2, 1)
    graph_.Insert_Node(4, 2)
    graph_.Insert_Node(4, 3)
    graph_.Topological_Sort()

有人能解释为什么我在没有修改字典的情况下仍会出现这个错误吗

Answer 1

简而言之：通过访问不存在的成员来更改defaultdict的大小

您正在执行以下操作：

1. 在self.adj_list上循环，这是一个defaultdict

2. 使用来自self.adj_list的节点调用Topological_Sort_Util（到目前为止还不错）

3. 在self.adj_list[input_node]

4. 使用节点的子节点递归调用Topological_Sort_Util

最后一步是在您的示例中出错的地方。节点1将节点3作为唯一的子节点，但您从未将节点3添加到adj_list。因为adj_list是一个defaultdict，所以

for child in self.adj_list[input_node]:

将为input_node添加一个新的键到adj_list，如果它还不存在的话。这会更改字典的大小，并引发异常

通过在调用Topological_Sort_Util之前和之后打印adj_list可以看到这一点：

defaultdict(<class 'list'>, {1: [3], 2: [1], 4: [2, 3]})  # before
defaultdict(<class 'list'>, {1: [3], 2: [1], 4: [2, 3], 3: []})  # after

您可以通过确保子节点存在于Insert_Node中来修复它：

def Insert_Node(self, u, v):
    self.adj_list[u].append(v)
    self.adj_list[v]

另一个问题

您的visited属性是一个list，它使用基于0的索引，但是您可以从1开始为节点编号。所以，当你这么做的时候

self.visited[input_node] = True

对于节点4，它将失败，因为list只有大小4（最后一个索引是3）

所以你要么需要

• 将visited转换为具有任意键或
• 确保visited足够大，可以索引到所有节点或节点
• 从0开始为节点编号