优先级队列与链表Java

priority queue vs linked list java(优先级队列与链表Java)

问题描述

我正在解决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;
                }   
            }
        }

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

推荐答案

如documentation所说：

基于优先级堆的无界优先级队列。的要素 优先级队列根据其自然顺序进行排序，或者 由队列构造时提供的比较器执行，具体取决于 使用了哪个构造函数。

LinkedList保留插入顺序，PriorityQueue不保留。因此，您的迭代顺序发生了变化，这使得您使用PriorityQueue的实现不同于BFS。

这篇关于优先级队列与链表Java的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持编程学习网！