优先级队列与链表Java [英] priority queue vs linked list java

查看:43
本文介绍了优先级队列与链表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的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!

查看全文
登录 关闭
扫码关注1秒登录
发送“验证码”获取 | 15天全站免登陆