Prim算法優先級隊列

Question

我想用優先級隊列在Java中實現Prim算法。

我找不到我的錯誤。 ：/我只是認識到隊列沒有正確排序節點。

例如用於圖：

0 4 7 5 
4 0 2 3 
7 2 0 1 
5 3 1 0 

它始終以作爲第二個中的節點4。所以它命令隊列像[node1，node4，node2，node3]而不是[node1，node2，node3，node4]。 我對優先級隊列做了什麼錯誤？

問候

public class PrimAlgorithm { 

     private static int[] par; // parent 
     private static int[] key; // value 
     private static int sum; 


     public static void prim(Graph g){ 

      Node[] nodes = g.getNodes(); 
      key = new int[g.getMatrix().length]; 
      par = new int[g.getMatrix().length]; 


        PriorityQueue<Node> queue = new PriorityQueue<Node>(42, new Comparator<Node>(){ 
         public int compare(Node v1, Node v2){ 
          return Integer.valueOf(key[v1.getId()-1]).compareTo(Integer.valueOf(key[v2.getId()-1])); 



      for (Node n : nodes) { 
       int x = n.getId()-1; 
       key[x] = 1000; 
       par[x] = 0; 
       queue.add(n); 
      } 

      key[0] = 0; 


      while(!queue.isEmpty()) { 
       Node n = queue.poll(); 

       List<Node> neighbours = n.getNeighbors(); 

       for (Node m : neighbours){ 
        if (queue.contains(m) && g.getEdge(n, m).getWeight() !=0 && g.getEdge(n, m).getWeight() < key[m.getId()-1]){ 

         par[m.getId()-1] = n.getId(); 
         key[m.getId()-1] = g.getEdge(n, m).getWeight(); 

        } 
       } 
      } 

      for (int i=0; i < key.length; i++){ 
       sum += key[i]; 
       } 

      System.out.println("Das Gewicht des minimalen Spannbaumes lautet: " + sum); 
      System.out.println("Der Spannbaum ergibt sich wie folgt: "); 
      //fängt ab 1 an sonst, hätten wir immer noch einen Nullknoten 
      for(int i=0; i <par.length; i++){ 
       System.out.println("Der Vorgänger von Knoten: " + " "+ (i+1) + "-> " + par[i] + " Gewicht " 
         + key[i]); 
      } 

     } 

     public static void main(String[] args) { 
      System.out.println("Prim Algorithmus zu Berechnung des minimalen Spannbaums."); 
      Graph g = new Graph(); 

      prim(g); 
     } 

} 

Answer 1

有幾件事情：

1. 在隊列內的PriorityQueue的默認實現不能重新排序項動態。換句話說，在添加項目後更改密鑰時，它不會導致隊列中已有的項目更改其排序。
2. 當您首次將節點添加到PriorityQueue中時，它們都具有相同的優先級。因此，根據用於PriorityQueue中的API，

如果多個元件被並列至少值，頭部是這些元素中的一個 - 方法是任意的。

因此，不保證節點的初始順序。如果你想要一個有效的Prim's實現，你不應該使用PriorityQueue的contains（）方法來檢查隊列內部，因爲這是一個O（N）操作。相反，使用布爾數組來跟蹤哪些項目在隊列中，哪些是O（1）查找。請注意，添加操作是有效的O（log（n）），而從隊列的前面除去的任何地方的移除是O（n）這應該避免。所以，一個好的技巧是保持一個布爾型visited []數組，其中如果節點i已經被處理，visited [i]爲真。然後，您可以多次添加相同的節點，因爲知道具有最低密鑰的節點將首先被檢索。如果當你輪詢一個節點的隊列時，visited [node.id]已經是true，那麼就直接跳過它。

當然，爲了使其工作，Node必須基於它包含的某個值而不是外部數組進行比較，以便可以在隊列中擁有兩個具有相同ID但具有不同鍵的節點。