java.util.PriorityQueue的元素不会在轮询时向上移动（）

Question

我在图上实现了一个BFS，其中节点由状态类的对象标记（我实现了一个隐式等于方法进行比较）。

我已经实现了我的队列使用PriorityQueue与一个返回1的比较器，因为我想扩展程序来处理DFS，Astar等，我可以做的只是改变比较器内的逻辑

以下是相关代码：

//bfscompariator。JAVA

import java.util.Comparator;

public class BFSComparator implements Comparator<State>{
    @Override public int compare(State x, State y) {
       return 1;
    }
}

//解算器。JAVA

Comparator comparator = new BFSComparator();
PriorityQueue<State> frontierList = new PriorityQueue<State>(500,comparator); //List of nodes to be expanded
frontierList.add(seed state0);
while (!frontierList.isEmpty()){
        curState = frontierList.poll();
        //handle, expand and add child states to frontierList

在遍历列表并打印当前元素时，我发现有些元素没有上移（例如，poll上的{a，b，c，d，e}变成poll（）上的{b，e，c，d}，而不是{b，c，d，e}），因此它不执行FIFO。

for(State x:frontierList) {
             //print x
}

1） 我的比较仪有问题吗？

2） 有没有更好的方法来实现这一点？i、 例如，一个比优先级队列更好的容器，我可以在更改排序背后的逻辑时添加它，而不是使用具有不同调用名（如push和pop）的队列和堆栈？这将有助于我以后根据启发法对它们进行排序。或者我应该使用链表并执行基于插入排序的方法吗？

编辑：我想说得更清楚一点。我正在尝试实现一个集合，我可以通过一个公共的add（State）或State x=remove（）来实现它，而不考虑DFS或BFS（FIFO或LIFO）或其他基于优先级的算法，如a-Star和Beam搜索。

我可能会扩展集合并实现add和其他方法。

Answer 1

public int compare(State x, State y)

此方法返回正值表示x

我觉得你应该用队列来申报边境名单

当你需要DFS时，使用LinkedList

当您需要BFS时，请使用PriorityQueue