Kruskal在Python中的算法

最近我已經學習了關於圖論的知識，並試圖實現Kruskal算法來找到最小值。使用權重矩陣生成圖中的生成樹。我爲矩陣獲得了正確的輸出，併爲另一個輸出了出界誤差！它給了我一個錯誤：Kruskal在Python中的算法

[[1000,16,12,21,1000,1000,1000],[16,1000,1000,17,20,1000,1000],[12,1000,1000,28,1000,31,1000],[21,17,28,1000,18,19,23],[1000,20,1000,18,1000,1000,11],[1000,1000,31,19,1000,1000,27],[1000,1000,1000,23,11,27,1000]]

矩陣對我有一個正確的答案是下面的一個：（注：1000是用來表示無窮

vertices=5 
spset=[True]*5 
wt=[[1000,1,3,4,1000],[1,1000,5,1000,7],[3,5,1000,6,8],[4,1000,6,1000,2],[1000,7,8,2,1000]] 


row=[0] 

for i in xrange(vertices-1): 
    row_num,col_num,min_no=-1,-1,1000 
    for i in row: 
    temp=min(wt[row[i]]) 
    if(min_no>temp): 
     min_no=temp 
     row_num=i 
     col_num=wt[i].index(temp) 
    print str(min_no)+"("+str(row_num)+","+str(col_num)+")" 
    spset[col_num]=False 
    wt[col_num][row_num]=1000 
    for i in xrange(vertices): 
    wt[i][col_num]=1000 
    row.append(col_num) 

d=raw_input()

來源

2014-01-28 vvv

提示：避免代碼中的空白不會讓它運行得更快。這隻會讓閱讀變得更難:-) –

的重量在下面的代碼塊，

for i in row: 
    temp=min(wt[row[i]])

i被遍歷的row元素。如果row有兩個要素[0,2]，那麼當i變成2時，row[i]將給出IndexError: list index out of range。

如果要遍歷row的元素，請改爲使用for i in range(len(row))。

來源

2014-01-28 11:03:26

Kruskal在Python中的算法

回答

相關問題