优先级队列 vs 链表 java

Question

我正在解决 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 && 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 && visited[k]==0)
                {
                    dist[k]=dist[u]+1;
                    q.add(k);
                    visited[k]=1;
                }   
            }
        }

另外，当我使用邻接列表而不是邻接矩阵时，优先队列实现给出了正确的答案。

Answer 1

正如 documentation 所说：

An unbounded priority queue based on a priority heap. The elements of the priority queue are ordered according to their natural ordering, or by a Comparator provided at queue construction time, depending on which constructor is used.

LinkedList 保留插入顺序，PriorityQueue 不保留。所以你的迭代顺序改变了，这使得你的实现使用 PriorityQueue 而不是 BFS。

Answer 2

你的问题基本上是：为什么你认为两个任意 classes 很好，最终是 different classes 。 .做同样的事情？！

换句话说：你今天的教训应该是：你不应该联系其他人来解释你的实验。更好的方法是：在那个时间点，当你编写你的代码时，你最好确保你理解每个你的代码的细节代码。

含义：当您开始使用 Java 库中的新 class 时，go 并阅读它的 javadoc！当你不预先做这些，而是直接开始你的实验时；然后你运行大吃一惊：那就查查吧。

当然，让其他人向您解释这一点很方便，但是成为一名优秀程序员的本质是内在动力亲自了解您的代码正在（或将要）做什么！

当然，您的问题的答案是：您的两个示例使用了 不同的 种列表，这些列表具有 不同的 行为;如相应的 Javadoc (this versus that).

中所述

Answer 3

PriortiyQueue 和 Linkedlist 实现队列接口并以与队列（FIFO）相同的方式执行操作。 PriorityQueue 和 Linkedlist 之间的区别是在插入时 PriorityQueue 将按照自然顺序进行排序和排序，但我们也可以添加一个比较器来定义记录的特定排序顺序，而 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]

优先级队列 vs 链表 java

priority queue vs linked list java

java

algorithm

graph

graph-algorithm

data-structures