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

Question

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

我写了我的Comparator，它使用一个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()以确保传递性的方式编写我的方法？

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

Answer 1

如何以确保传递性的方式编写compare()方法？

正如您所发现的，a 的契约Comparator迫使您根据两个给定对象做出决定，而它们在总体排序中的关系可能涉及其他对象。

这里有一个 DAG，而你要做的是拓扑排序。我认为使用 a 的唯一方法是Comparator首先进行拓扑排序，然后在实现比较器时使用此排序中对象的索引作为键。但是，当然不需要比较器，因为您已经对元素进行了排序。