迭代期间字典大小已更改

Question

在我的一生中，我无法理解Python认为我的dict在迭代过程中是如何改变大小的。我试着重新编写了几次代码，但不知道要在哪里修改字典。在

概述：我正在研究一种分层聚类算法，在该算法中，我从已创建的图中构建一个MST，然后移除弱于指定阈值的边。这一切似乎都很好，但是现在当我在检查并计算clusters（列表列表）时，我遇到了这个非常奇怪的错误。以下是我的代码：

def compute_clusters(self):
    """ wrapper function to compute clusters via DFS """
    mst = self.mst
    total_nodes = len(mst.keys())
    visited = set()
    for node in mst.keys():
        if node not in visited:
            self.clusters += self.cluster_dfs(mst, node, visited)

def cluster_dfs(self, mst, node, visited, cluster=[]):
    """ creates clusters through dfs """
    cluster.append(node)
    if self.dfs_finished(mst, node, visited):
        return cluster
    for neighbor in self.mst[node].keys():
        if neighbor not in visited:
            visited.add(neighbor)
            cluster.append(neighbor)
            self.cluster_dfs(mst, neighbor, visited, cluster)

def dfs_finished(self, mst, node, visited):
    for neighbor in self.mst[node].keys():
        if neighbor not in visited:
            return False
    return True

基本上，mst是我的MST（defaultdict（dict））的副本，它将所有节点映射到邻居：权重。在

我想一个简单的方法是从MST中尚未被DFS触及的每个节点执行DFS。根据这种逻辑，递归只会在访问了特定集群中的所有元素之后返回。然后它转到下一个集群并执行DFS。在

我的运行时错误是：

^{pr2}$

有人看到我可能不小心修改dict的地方吗？如果这是一个愚蠢的错误道歉-我有点累了。在

Answer 1

我想错误就在这里：

for neighbor in self.mst[node].keys():
                     ^^^^^^^^^
    if neighbor not in visited:
        self.cluster_dfs(mst, neighbor, visited, cluster)
                         ^^^

mst[node]有键neighbor，但这对mst本身来说并不一定是真的

Answer 2

Does anyone see a spot where I could maybe be accidentally modifying the dict?

假设mst是defaultdict，一个可能的疑点是：

for neighbor in self.mst[node].keys():

因为这会增加node到{}。如果这就是问题所在，那么剩下的问题是如何；对于更多的上下文/mst设置可能会有所帮助。在

---

似乎是这样，访问一个不存在的键到defaultdict会添加该键。。。。一个mcve。。在

^{pr2}$