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)