Python - 用數組執行Prim的算法

我正在試圖用Python 3實現Prim的算法，它計算它生成的MST的總權重。我正在做一些不尋常的事情，用一個「數組」來跟蹤未訪問的節點。Python - 用數組執行Prim的算法

這裏是我的代碼：

def Prim(Graph): 
    # row 1 is "still in R" 
    # row 2 is the connector vertex 
    # row 3 is the cost 
    total = 0 
    A = [] 
    n = len(Graph) 
    A = [[None for x in range(0, n)] for y in range(1, 4)] 
    #Debugging purposes 
    #print(A) 
    for x in range(1, n): 
     A[0][x] = 'Y' 
     A[1][x] = 0 
     A[2][x] = 0 

    for neighbour in Graph[1]: 
     A[1][neighbour-1] = 1 
     A[2][neighbour-1] = Graph[1][neighbour] 
     #Debugging purposes 
     #print("Neighbour: ", neighbour, "Weight: ", Graph[1][neighbour]) 
    current = 1 
    T = [current] 
    MST_edges = {} 
    count = 0 
    while len(T) < n: 
     x = search_min(current, A) 
     T.append(x) 
     MST_edges[x] = A[1][x] 
     A[0][x] = 'N' 
     total += A[2][x] 

     #print(Graph) 
     #print(A) 
     for neighbour in Graph[x]: 
      #print(neighbour) 
      #print(A[2][neighbour-1]) 
      if A[0][neighbour-1] != 'N': 
       if Graph[x][neighbour] < A[2][neighbour-1]: 
        A[1][neighbour-1] = x 
        A[2][neighbour-1] = Graph[x][neighbour] 
     count += 1 
     current = T[count] 
    return total 



def search_min(current, A): 
    minimum_cost = 100 
    minimum_vertex = 1 
    for x in range(1,len(A[0])): 
     if A[1][x] != None and A[0][x] != 'N' and A[2][x] < minimum_cost: 
       minimum_cost = A[2][x] 
       minimum_vertex = x 
       #Debugging 
    ##   print("x", x) 
    ##   print("cost",minimum_cost) 
    ##   print("vertex",x) 
    return minimum_vertex

這有時讓我低得離譜的重量比如20（這幾乎是不可能的，因爲所有邊的最低重量爲10）。問題可能是在while循環中：

while len(T) < n: 
     x = search_min(current, A) 
     T.append(x) 
     MST_edges[x] = A[1][x] 
     A[0][x] = 'N' 
     total += A[2][x] 

     #print(Graph) 
     #print(A) 
     for neighbour in Graph[x]: 
      #print(neighbour) 
      #print(A[2][neighbour-1]) 
      if A[0][neighbour-1] != 'N': 
       if A[2][neighbour-1] != None and Graph[x][neighbour] < A[2][neighbour-1]: 
        A[1][neighbour-1] = x 
        A[2][neighbour-1] = Graph[x][neighbour] 
     count += 1 
     current = T[count]

但我不知道什麼部分。越來越遲，我的頭痛，任何能夠幫助的人都會很棒。

編輯下面是它生成的MST的一個例子。由於某些原因，存在具有0加權邊的頂點。

graph = construct_graph（20） Prim（圖）{3：0,5：0,8：0,16：0,6：5,9：3,7：8,11：5,15： 11,12：11,2：8,18：2,19：2,1：19,10：19,14：10,17：5,13：16,4：1}

（看着我代碼仔細，你可以看到，對於值x：y，x是頂點的值，而y是連接邊的權重由於某種原因，有頂點加權0）

來源

2017-04-08 RosaryLightning X

你可以舉一個圖表的例子來計算錯誤的權重嗎？也許你應該讓函數返回它找到的樹，而不僅僅是重量，這樣你就可以看到它出錯了（這可能會告訴你它在哪裏犯錯）。嘗試'返回總數，A'（或者用'MST_edges'）。 – Blckknght

@Blckknght嗨，感謝您的建議，我添加了它生成的MST的一個例子 –

在建議之後，我改變了這個代碼行：

A[2][x] = 0

要這樣：

A[2][x] = math.inf

這是爲了讓數組不小心看到「0的權重活泉，邊緣」因爲這應該意味着它沒有連接。所以這是非常重要的。

來源

2017-04-08 17:21:07

Python - 用數組執行Prim的算法

回答

相關問題