I am getting "RuntimeError: dictionary changed size during iteration" despite not making any changes to the dictionary. How do i resolve this?

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 的大小。

您正在执行以下操作：

循环 self.adj_list，这是（尽管名称）一个 defaultdict
使用来自 self.adj_list 的节点调用 Topological_Sort_Util（目前一切顺利）
遍历 self.adj_list[input_node]
用节点的子节点递归调用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开始编号

I am getting "RuntimeError: dictionary changed size during iteration" despite not making any changes to the dictionary. How do i resolve this?

I am getting "RuntimeError: dictionary changed size during iteration" despite not making any changes to the dictionary. How do i resolve this?

python

runtime-error

topological-sort

python-3.x

另一个问题