Karger의 최소 컷 알고리즘

Question

파이썬 Karger의 최소 컷 알고리즘을 구현하는 동안, 나는이 최소 컷이 5 것을 의미합니까

edgelist remaining: [[11, 20], [11, 20], [20, 11], [20, 11], [20, 11]] 
nodelist remaining: [11, 20] 

로 출력을 무엇입니까?

with open('foo1.txt') as req_file: 
    mincut_data = [] 
    for line in req_file: 
     line = line.split() 
     if line: 
      line = [int(i) for i in line] 
      mincut_data.append(line) 

#extracting edges from the data #    
edgelist = [] 
nodelist = [] 
for every_list in mincut_data: 
    nodelist.append(every_list[0]) 
    temp_list = [] 
    for temp in range(1,len(every_list)): 
     temp_list = [every_list[0], every_list[temp]] 
     flag = 0 
     for ad in edgelist: 
      if set(ad) == set(temp_list): 
       flag = 1 
     if flag == 0 : 
      edgelist.append([every_list[0],every_list[temp]]) 


#karger min cut algorithm# 
while(len(nodelist) > 2): 
    val = randint(0,(len(edgelist)-1)) 
    print (val) 
    target_edge = edgelist[val] 
    replace_with = target_edge[0] 
    should_replace = target_edge[1] 
    for edge in edgelist: 
     if(edge[0] == should_replace): 
      edge[0] = replace_with 
     if(edge[1] == should_replace): 
      edge[1] = replace_with 

    nodelist.remove(should_replace) 
    for i in range((len(edgelist)-1),-1,-1): 
     if edgelist[i][0] == edgelist[i][1]: 
      edgelist.remove(edgelist[i]) 

print ('edgelist remaining: ',edgelist) 
print ('nodelist remaining: ',nodelist) 

내가 파이썬 Karger의 알고리즘을 배우려고 노력하고 있어요하지만 난이 맞는지 확실하지 않다 : 나는 다음과 같은 코드를 사용하고 있습니다.

Answer 1

나는 대답을 찾았습니다. 남아있는 가장자리 목록은 최소 절단 인 것 같습니다. Karger의 알고리즘이 무작위 알고리즘이므로, 최상의 솔루션을 얻으려면 프로그램을 여러 번 실행해야합니다.