java - 优先队列与链表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。