Блог

Я решал BFS проблему. Я использовал PriorityQueue, но получал неправильный ответ, затем я использовал LinkedList , я получил правильные ответы. Я не могу найти разницу между ними. Вот оба кода. Почему оба ответа разные?

 Code1:    
        LinkedList q=new LinkedList();
        q.add(src);
        dist[src]=0;
        visited[src]=1;
        while(!q.isEmpty()){
            u=(int)(Integer) q.remove(0);
            for (int k = 0; k < n; k  ) {
                if(a[u][k]==1 amp;amp; visited[k]==0)
                {
                    dist[k]=dist[u] 1;
                    q.add(k);
                    visited[k]=1;
                }   
            }
        }

Code 2: 
    PriorityQueue<Integer> q= new PriorityQueue<>();
        q.add(src);            
        dist[src]=0;
        visited[src]=1;
        while(!q.isEmpty()){
            u=q.remove();               
            for (int k = 0; k < n; k  ) {
                if(a[u][k]==1 amp;amp; visited[k]==0)
                {
                    dist[k]=dist[u] 1;
                    q.add(k);
                    visited[k]=1;
                }   
            }
        }
  

Также, когда я использовал список смежности вместо матрицы смежности, реализация очереди приоритетов давала правильные ответы.

Как говорится в документации:

Неограниченная приоритетная очередь, основанная на куче приоритетов. Элементы приоритетной очереди упорядочиваются в соответствии с их естественным порядком или с помощью компаратора, предоставляемого во время построения очереди, в зависимости от того, какой конструктор используется.

LinkedList сохраняет порядок вставки, PriorityQueue — нет. Итак, порядок ваших итераций меняется, что делает вашу реализацию, использующую PriorityQueue, чем-то отличным от BFS.

PriortiyQueue, а также Linkedlist реализуют интерфейс очереди и выполняют операции таким же образом, как и очередь (FIFO). Разница между PriorityQueue и Linkedlist заключается в том, что во время вставки PriorityQueue будет отсортирован, а также упорядочен в соответствии с естественным порядком, но мы можем добавить Commparator также для того, чтобы определить конкретный порядок сортировки для записи, в то время как в качестве LinkedList будет просто упорядочен. Итак, пока вы пытаетесь добавить элементы в PriorityQueue, они будут отсортированы на основе их естественного порядка или в соответствии с функцией сравнения.

 import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;

public class QueueInJava {

public static void main(String[] args) {
    Queue<String> queue = new LinkedList<>(); 
    queue.add("Ishfaq");
    queue.add("Ramzan");
    queue.add("Nagoo");
    queue.add("Bangalore");
    
    System.out.println("Linked List Queue is:"   queue);
    System.out.println("Linked List Queue Peek is :"   queue.peek());
    
    queue.poll();
    System.out.println("Linked List Queue after remove is:"   queue);
    
    
    Queue<Integer> queuenew = new PriorityQueue<>();
    
    
    queuenew.add(2);
    queuenew.add(3);
    queuenew.add(1);
    queuenew.add(0);
    queuenew.add(4);
    
    System.out.println("Priority Queue is:"   queuenew);
    System.out.println("Priority Queue Peek is :"   queuenew.peek());
    
    int ieleFirst=queuenew.remove();
    System.out.println("Priority Queue Element Removed is:"   ieleFirst);
    int ieleSecond=queuenew.remove();
    System.out.println("Priority Queue Element Removed is:"   ieleSecond);
    System.out.println("Priority Queue after remove is:"   queuenew);
  }

}
  

Вывод:

 Linked List Queue is: [Ishfaq, Ramzan, Nagoo, Bangalore]

Linked List Queue Peek is: Ishfaq

Linked List Queue after remove() is: [Ramzan, Nagoo, Bangalore]

Priority Queue is: [0, 1, 2, 3, 4]

Priority Queue Peek is: 0

Priority Queue Element Removed is: 0

Priority Queue Element Removed is: 1

Priority Queue after remove() is: [2, 3, 4]
  

Ваша проблема в основном: почему вы думаете, что два произвольных класса, которые, ну, в конце концов, являются разными классами .., делают одно и то же?!

Другими словами: ваш урок сегодня должен быть таким: вы не должны обращаться к другим людям, чтобы объяснить свои эксперименты. Лучший подход таков: в тот момент времени, когда вы пишете свой код, вам лучше убедиться, что вы понимаете каждую деталь вашего кода.

Значение: когда вы начнете использовать новый класс из библиотек Java, перейдите и прочитайте его javadoc! И когда вы не делаете этого заранее, а сразу начинаете свои эксперименты; и вы сталкиваетесь с сюрпризами: тогда ищите вещи.

Конечно, удобно, когда вам это объясняют другие люди, но суть хорошего программиста заключается в внутренней мотивации самому выяснить, что делает (или будет делать) ваш код!

И, конечно, ответ на ваш вопрос таков: в ваших двух примерах используются списки разного типа, которые имеют разное поведение; как указано в их соответствующем Javadoc (это по сравнению с тем).