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但具有不同键的节点。