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将包含对原始列表的引用，而不是它们的副本。

要执行深副本，您可以使用deepcopy：

from copy import deepcopy 
... 

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