priority queue vs linked list java

Question

I was solving BFS problem. I used PriorityQueue but I was getting wrong answer, then I used LinkedList, I got right ans. I'm unable to find the difference between them. Here are both the codes. Why both the answers are different?

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;
                }   
            }
        }

Also when I used Adjacency List instead of Adjacency matrix, Priority Queue implementation gave right ans.

Answer 1

As the documentation says:

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 preserves the insertion order, PriorityQueue does not. So your iteration order changes, which makes your implementation that uses PriorityQueue something other than BFS.

Answer 2

PriortiyQueue as well as Linkedlist implement the Queue Interface and perform operations same the way as a Queue (FIFO). The difference between PriorityQueue and Linkedlist is at the time of insertion PriorityQueue will be sorted as well as ordered as per the natural order but we can add a Commparator also in order to define the particular order of sorting for a record, while as LinkedList will be just ordered. So while you are trying to add elements in PriorityQueue, they will get sorted on the basis of their natural order or as per the comparator function.

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);
  }

}

Output:

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]