Приоритет очередей Prim Algorithm

Question

Я пытаюсь реализовать алгоритм Prim в Java с приоритетной очередью.

Я не могу найти свою ошибку. :/Я просто признаю, что очередь не упорядочивает узлы правильно.

пример графа:

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, они имеют одинаковый приоритет. Таким образом, в соответствии с API для PriorityQueue,

Если несколько элементов привязаны к наименьшему значению, головка является одним из тех элементов - связи разбиты произвольно.

Таким образом, нет гарантии первоначального заказа узлов.

3. Если вы хотите эффективную реализацию Prim, вам не следует использовать метод contains() PriorityQueue для проверки внутри очереди, поскольку это операция O (N). Вместо этого используйте булевский массив, чтобы отслеживать, какие элементы находятся в очереди или нет, который является поиском O (1).

Для эффективного способа переупорядочения очереди обратите внимание, что операция добавления - это O (log (n)), которая эффективна, а удаление из любого места, кроме передней части очереди, - O (n) чего следует избегать. Таким образом, хороший трюк состоял бы в том, чтобы сохранить массив boolean visited [], где [i] был указан true, если Node i уже обработан. Затем вы можете добавить один и тот же узел несколько раз, зная, что первый с самым низким ключом будет восстановлен первым. Если при опросе очереди для узла, посещение [node.id] уже верно, то просто пропустите его.

Конечно, для того, чтобы это сработало, узел должен быть сопоставим на основе некоторого значения, которое он содержит, а не внешнего массива, так что вы можете иметь два узла с одним и тем же идентификатором в очереди, но с другим ключом.