找到一個圖的最小權重

我想製作一個程序，它使用Kruskal算法計算最小跨度重量，我已經按照遞增的順序使用他們的weghts對邊進行了排序，並將其放入2d列表中。後來我也寫一個方法使用sortededge，採取樣本，sortededge = [['1', '2', '1'], ['5', '6', '1'], ['2', '4', '2'], ['3', '6', '2'], ['3', '5', '3'], ['4', '6', '3'], ['3', '4', '5'], ['1', '3', '6']] 方法是找到一個圖的最小權重

vertexcheck = [] 
minimumdistance = 0 
def MSW: 
    for i in range(len(sortededge)): 
     if (sortededge[i][0] not in vertexcheck) or (sortededge[i][1] not in vertexcheck): 
      if (sortededge[i][0] not in vertexcheck): 
       vertexcheck.append(sortededge[i][0]) 


      if (sortededge[i][1] not in vertexcheck): 
       vertexcheck.append(sortededge[i][1]) 
      minimumdistance += int(sortededge[i][2])

拿到最低的重量，但它亙古不變的工作，爲所有的圖表和我將歡迎任何幫助

來源

2014-12-12 Kal

歡迎計算器！您可以使用編輯器中的「{}」按鈕以可讀方式格式化代碼。請具體說明「不行」的含義;代碼失敗的例子是什麼？這個例子的實際和預期結果是什麼？ – 2014-12-12 23:34:45

你的算法實現是錯誤的。

讓一個例子，其中的算法中失敗：

enter image description here

和邊緣看起來是這樣排序後：

邊緣：

1, 2, 1 
    3, 4, 2 
    2, 3, 5

在第一次迭代

你會把1和2在你的vertexcheck中。在第二次迭代中更新vertexcheck = [1,2]
，你將把3和4放在你的vertexcheck中。更新vertexcheck = [1,2,3,4]
但在第三次迭代，你可以不加2-> 3的邊緣，因爲這兩個頂點出現在您vertexcheck。

這就是爲什麼你的實現給錯誤輸出:(

實際上，對於克魯斯卡的實現，你需要知道和使用稱爲聯盟查找數據結構算法，它告訴你，如果你正在嘗試連接當前節點已經連接:)

如果他們已經連接然後跳過優勢，因爲他們已經用低成本的:)否則將它們連接連接...

由於很多實現可供MST使用python ，我不會打擾給你一個:)

你可以在這裏找到僞代碼： Kruskal's_algorithm

以及範例： Kruskal's_implementation

來源

2014-12-14 06:48:44

找到一個圖的最小權重

回答

相關問題