Java PriorityQueue 的顺序似乎有误

Question

我正在尝试制作一个解决最小生成树问题的程序。为此，我有一个 Edge 对象的优先级队列，应该根据它们相应的权重字段对其进行排序（之后它并不重要，但我一直在按节点名称进行排序）。

我正在使用 java.util.PriorityQueue。我已经尝试了几乎所有的方法，但我想不出实现 compareTo() 函数的方法。它对大部分边进行了正确排序，但不是全部。这是我能想到的最基本的 compareTo() 函数的代码：

@Override
public int compareTo(Object other) {
    return toString().compareTo(((Edge) other).toString());
}

toString()函数首先输出权重，然后输出两个节点，所以如果两个节点 A 和 B 以权重 4 连接，它将输出

4AB

放入示例图后，我得到以下优先级队列：

[1AB, 1BA, 1FH, 2CB, 1CG, 1GC, 1HF, 2EB, 2CD, 3EG, 2BC, 2BE, 3AC, 2GH, 2HG, 5AD, 5EC, 3ED, 2EF, 5CE, 4FD, 2FE, 4FG, 5DA, 2DC, 3GE, 4GF, 3DE, 3CA, 4DF]

显然这不是按顺序排列的，但基本上我能想到的每一种比较方法都会产生这个结果。

Answer 1

这里没有任何问题。您正在打印的内容似乎是 toString() 的结果，不保证其按任何特定顺序排列。

但是，当您通过移除或查看头部来使用队列时，将产生一个由您的比较器定义的最小元素。整个队列是无序的；顺序只决定了队列的head，只有某些指定在头部操作的操作才会受顺序影响。 toString() 和 iterator() 方法不在这些操作中。

您的比较器应该以数字方式而不是字符串方式比较权重。对边使用字符串比较作为具有相等权重的边的决胜局是可以的，但要考虑是否有两个方向相反的边，以及它们是否需要特别注意。

Java PriorityQueue 的顺序似乎有误

Java PriorityQueue appears to be in the wrong order

java

priority-queue

compareto

minimum-spanning-tree