在python中實現無限循環尋找路徑壓縮

我正在Python中實現Dijkstra和Kruskal算法，以找到隨機圖（常規圖和密集圖）中的最大帶寬路徑。但是，當我運行Kruskal算法來生成最大生成樹並調用操作查找時，它會在查找操作的循環內部導致無限循環（這發生在常規圖或密集圖中）。這個錯誤很奇怪，因爲之前一切都在工作，有時候查找操作對於這兩個圖都能正常工作。我按照課堂上給出的僞代碼實現了查找操作。我的代碼部分是：在python中實現無限循環尋找路徑壓縮

class Disjoint: 
    def __init__(self,size): 
     """ 
     Equivalent to MakeSet 
     Vertices are numbered from 1 to size 
     """ 
     self.parent = [0]*(size+1) 
     self.rank = [0]*(size+1) 

    def find(self,v): 
     R = [] #stack 
     r = v 

     while self.parent[r] != 0: 
      #sometimes this loop never stops (infinite loop) 
      R.append(r) 
      r = self.parent[r] 

     while len(R) != 0: 
      w = R.pop() 
      self.parent[w] = r 
      del w 

     del R 
     #del w 
     return r 

    def __del__(self): 
     del self.parent 
     del self.rank

UPDATE：固定的問題，查找功能是正確的。這個問題是我在克魯斯卡爾函數中遇到的邏輯錯誤。

來源

2014-11-23 kdol

while self.parent[r] != 0: 
     #sometimes this loop never stops (infinite loop) 
     R.append(r) 
     r = self.parent[r] 

while self.parent[r] == 0: 
     break 
else: 
     R.append(r) 
     r = self.parent[r]

來源

2014-11-23 04:40:02 Cris

謝謝，我試過，但還是不行:( – kdol 2014-11-23 05:52:02

if self.parent[r] == 0: 
    pass 
    #print("error", self.parent[r]) 
else: 
    while self.parent[r] (equal to or greater) 1: 
     R.append(r) 
     r = self.parent[r] 
    else: 
     #print("error", self.parent[r])

附言：我只是一個學生，剛畢業的證書IV網絡IT

來源

2014-11-23 06:15:10 Cris

固定的問題，這個問題是在功能克魯斯卡不在查找操作中，但再次感謝您花時間幫助我:)。 – kdol 2014-11-23 06:23:34

在python中實現無限循環尋找路徑壓縮

回答

相關問題