如何编写一个传递比较器，当“相等性”意味着“顺序无关”时？

Question

我有一组项目被序列化到文件中。某些项目会依赖于其他项目，但不允许循环引用。因此，它们需要以这样的方式进行序列化，即如果A依赖于B，则B首先在文件中进行序列化。

我编写了一个比较器，使用reliesOn()函数确定两个项目是否关联：

Collections.sort(itemsToSort, new Comparator<Item>() {
    @Override
    public int compare(Item first, Item second) {
        boolean firstReliesOnSecond = reliesOn(first, second);
        if (firstReliesOnSecond) {
            return 1;
        }
        boolean secondReliesOnFirst = reliesOn(second, first);
        if (secondReliesOnFirst) {
            return -1;
        }
        return 0;
    }
});

这在某些情况下是有效的，但并非所有情况都适用。在调试中，很明显排序依赖于 Comparator 的传递性，并且可以理解为不会比较每个可能的项目对。

例如，对于五个项目 A 到 E，如果：

A -> B
B -> E
C
D
E

那么一种可能的顺序是：

E, B, A, C, D

至少，E在B之前，B在A之前。

然而，在比较阶段（以一个例子来解释），发生的是将C与E进行比较，返回0，因为它们没有关系。然后将C与B进行比较，并且也返回0。

结果，排序算法假定B = E，这并非事实。（即使我违反了Comparator合同）。我该如何编写我的compare()方法以确保传递性？

编辑：有人指出我正在对有向无环图进行拓扑排序。我回想起了我的数据结构课程。幸运的是，维基百科似乎有一个很好的线性时间算法来执行这个排序——我会尝试一下。

- Craig Otis

---

顺便提一句，假设 B = E 的不是“比较器（Comparator）”，而是排序算法本身。（实际上，“比较器”代码非常少） - user253751

你说得对 - 我想这是排序算法和Comparator应该满足的约定的结合。我会更新我的措辞，谢谢！ - Craig Otis

你可以访问 Item 的相关对象吗？是否有像 getParents() 这样的方法？ - aioobe

你不能使用排序。你必须先穿过整个森林，然后收集所有的叶子。 - njzk2

@aioobe 所以投票关闭为重复问题？ - user253751

除非情况十分明确，否则我倾向于在关闭投票方面保守。在这种情况下，我将让原帖作者自行决定另一个主题中的答案是否回答了他在这里的问题。 - aioobe

Answer 1

我如何编写比较方法（compare() method），以确保传递性？

正如你已经发现的，Comparator的合同强制你基于两个给定对象做出决策，而它们在整体排序中的关系可能涉及其他对象。

你所面对的是一个DAG（有向无环图），你尝试的是一个拓扑排序。我唯一能想到的使用Comparator实现拓扑排序的方法是先进行拓扑排序，然后使用这个排序中对象的索引作为实现比较器时的键。但是当然，既然你已经排序了元素，就没有必要再使用比较器了。

- aioobe

---

谢谢你，你带我来到了正确的地方。（时间限制结束后会标记为已回答。） - Craig Otis

你能访问每个“Item”的“父级”吗？ - aioobe

是的，我们有一个访问者/实用方法可以找到它们。 - Craig Otis

那么，也许可以通过检查从对象2到根（或反之亦然）的路径上是否找到对象1来解决它。但是，1）这只是一个复杂和次优的拓扑排序实现，2）您需要一种解决兄弟顺序的方法。 - aioobe

Answer 2

破坏比较器的契约对你没有太大帮助，因为标准排序算法假定你会遵守它。

除了从维基百科实现拓扑排序算法外，您还可以查看this库（每当有人谈论有向图和拓扑排序时都会提到）或that实现。

- Jeor Mattan