priority queue vs linked list java
algorithm, data-structures, graph, graph-algorithm, java
Solution
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.
Problem
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.