每次迭代后修改的 Python 原始词典

Question

我尝试实现Karger的算法来计算python图形的最小切割，并用一个小的输入图测试了我的代码。基本上，我为每次迭代制作原始输入图的副本，但是在运行一次迭代的代码后，原始输入图以某种方式被修改。我的代码哪里出错了？

import random
def random_contraction(graph):
    u = random.choice(graph.keys())
    v = random.choice(graph[u])
        for node in graph[v]:
        for vertex in graph[node]:
            if vertex == v:
                graph[node].remove(vertex)
                graph[node].append(u)
    graph[u] = graph[u] + graph[v]
    graph[u] = [node for node in graph[u] if (node != u and node != v)]
    graph.pop(v, None)
def min_cut(graph):
    while len(graph) > 2:
        random_contraction(graph)
    node = random.choice(graph.keys())
    return len(graph[node])
graph_input = {0:[1,3,4,5], 1:[0,2,4],2:[1,3,5],3:[0,2],4:[0,1],5:[0,2]}
list_min_cut = []
for dummy_idx in range(100):
    print "original", graph_input 
    #check the original input graph at the beginning of iteration
    graph = dict(graph_input)
    #make a copy of original input graph
    list_min_cut.append(min_cut(graph))
print min(list_min_cut)

Answer 1

当您使用 dict() 进行复制时，它只会创建一个浅拷贝。这意味着复制不是递归完成的，因此新dict将包含对原始列表的引用，而不是它们的副本。

要执行深层复制，您可以使用深度复制：

from copy import deepcopy
...
for dummy_idx in range(100):
    print "original", graph_input 
    graph = deepcopy(graph_input)