Я получаю «RuntimeError: словарь изменил размер во время итерации», несмотря на то, что я не вносил никаких изменений в словарь. Как мне решить это?

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. L oop сверх self.adj_list, что (несмотря на название) является defaultdict

2. Вызовом Topological_Sort_Util с узлом из self.adj_list (до сих пор) так хорошо)

3. L oop над детьми в self.adj_list[input_node]

4. Вызовите Topological_Sort_Util рекурсивно с детьми узла

Последний шаг, где вещи go не так в вашем примере. Узел 1 имеет узел 3 как единственный дочерний элемент, но вы никогда не добавите узел 3 к adj_list. Поскольку adj_list является defaultdict, строка

for child in self.adj_list[input_node]:

добавит новый ключ для input_node в adj_list, если он еще не существует. Это изменяет размер словаря, и выдается исключение.

Это можно увидеть, напечатав adj_list до и после вызова Topological_Sort_Util:

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