なぜdata = copy.deepcopy（G）はKarger min cutアルゴリズムの問​​題ですか？

Question

karger min cut algorithm in python 2.7投稿された最小カットを計算するコードは次のとおりです。 data = copy.deepcopy（G）がなければ、最小カットを見つける効率は良くありません。なぜ誰かが説明できますか？ありがとう。

import random, copy 
data = open("***.txt","r") 
G = {} 
for line in data: 
    lst = [int(s) for s in line.split()] 
    G[lst[0]] = lst[1:] 

def choose_random_key(G): 
    v1 = random.choice(list(G.keys())) 
    v2 = random.choice(list(G[v1])) 
    return v1, v2 

def karger(G): 
    length = [] 
    while len(G) > 2: 
     v1, v2 = choose_random_key(G) 
     G[v1].extend(G[v2]) 
     for x in G[v2]: 
      G[x].remove(v2) 
      G[x].append(v1) 
     while v1 in G[v1]: 
      G[v1].remove(v1) 
     del G[v2] 
    for key in G.keys(): 
     length.append(len(G[key])) 
    return length[0] 

def operation(n): 
    i = 0 
    count = 10000 
    while i < n: 
     data = copy.deepcopy(G) 
     min_cut = karger(data) 
     if min_cut < count: 
      count = min_cut 
     i = i + 1 
    return count 


print(operation(100)) 

Answer 1

data = Gとkarger(data)辞書を重複しないとkarger(data)は元G辞書を使用します。しかしkargerはdataの値を自動的に変更するので、元の辞書の値が変更されます。従って、karger(data)の次回の実行では、異なる値の辞書を使用します。

deepcopyを削除し、karger(data)の前にprint(data)を追加すると、dataに異なる値が表示されます。