遍歷Prim的MST算法的鄰接矩陣

Question

我有一個遍歷Java加權鄰接矩陣的問題。我想要做的是使用Prim的算法從矩陣中獲得最小生成樹的權重。

我到目前爲止的代碼如下：

public int findPrim(int[][] matrix) { 

    ArrayList <Integer> checkThese = new ArrayList < >(); 
    checkThese.add(0); //Starting vertex. 
    boolean[] checked = new boolean[graph.vertexCount()]; 
    int w = 0; 
    int column = 0; 
    int row = 0; 
    int smallest = 0; 

    for (Iterator <Integer> it = checkThese.Iterator(); it.hasNext();) { 

    smallest = Integer.MAX_VALUE; 
    for (int k = 0; k < graph.vertexCount(); k++) { 

     if ((matrix[r][k] < smallest) && matrix[r][k] != 0 && !checked[k - 1]) { 
     smallest = matrix[r][k]; 
     column = k; 
     } 
    } 

    if (smallest != Integer.MAX_VALUE) { 
     w += smallest; 
     checkThese.add(column); 
     checked[column] = true; 
    } 
    } 

    return w; 
} 

我知道如何通過遍歷矩陣應該在紙面上的工作，但我有與執行問題。更具體地說，因爲我需要在遍歷列表時更新checkThese，所以我明白我需要爲它使用迭代器，就像我嘗試過的那樣。但是，現在的問題是，我無法找到一種方法來獲取矩陣的r座標，我稍後需要。該方法也缺少其他一些東西，但我主要關心的是如何在更新我檢查的矩陣行列表的同時遍歷矩陣。

我的鄰接矩陣是在

A B C D E 
A 0 4 2 8 0 
B 0 0 5 6 7 
C 0 0 0 9 3 
D 0 0 0 0 1 
E 0 0 0 0 0 

形式的計劃是先從A行，並選擇最小的邊緣（2）。之後，我將排除列C，並且接下來檢查行A和C等等，直到我排除所有列，從而檢查所有邊。

Answer 1

您需要另一個嵌套循環才能使其按照您指示的方式工作。這是修正的僞代碼。

let n be the number of vertices 
initialize cost <- 0 
initialize checkThese <- [0] 
initialize checked <- [true, false, ..., false] (length n) 
repeat n - 1 times (alternatively, test for termination as indicated) 
    smallest <- infinity 
    argSmallest <- null 
    for v in checkThese 
     for w from 0 to n - 1 
      let cost = matrix[min(v, w)][max(v, w)] 
      if not checked[w] and cost < smallest then 
       smallest <- cost 
       argSmallest <- w 
      end if 
     end for 
    end for 
    (break here if argSmallest is null) 
    cost <- cost + smallest 
    add argSmallest to checkThese 
    checked[argSmallest] <- true 
end repeat 

這不是Prim算法特別有效的實現。爲了加速它從O（n^3）到O（n^2），稠密矩陣的漸近最優值，可以維護另一個n元素的整數數組，稱它爲minCost。索引w處的條目是從檢查頂點到w的邊緣的最小成本。修改後的僞代碼看起來像這樣。

let n be the number of vertices 
initialize cost <- 0 
initialize checked <- [true, false, ..., false] (length n) 
initialize minCost <- [0, infinity, ..., infinity] (length n) 
repeat n - 1 times (alternatively, test for termination as indicated) 
    smallest <- infinity 
    argSmallest <- null 
    for w from 0 to n - 1 
     if not checked[w] and minCost[w] < smallest then 
      smallest <- minCost[w] 
      argSmallest <- w 
     end if 
    end for 
    (break here if argSmallest is null) 
    cost <- cost + smallest 
    checked[argSmallest] <- true 
    minCost[argSmallest] <- 0 
    for v from 0 to n - 1 
     let cost = matrix[min(argSmallest, v)][max(argSmallest, v)] 
     if not checked[v] and cost < minCost[v] then 
      minCost[v] <- cost 
     end if 
    end for 
end repeat 

如果所有的邊緣成本是肯定的，那麼你就可以minCost[w] > 0代替測試checked[w]，並廢除了checked陣列。你也可以融合兩個循環。