5

我有一组序列化到文件的项目。有些项目可以依赖其他项目，但不允许循环引用。因此，它们需要以某种方式进行序列化，如果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，并且可以理解的是不会比较每个可能的项目配对。

例如，通过 5 个项目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()。）如何以确保传递性的方式编写我的方法？

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

4

2 回答 2

2

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

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

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

于 2015-01-22T21:53:33.213 回答
0

打破合同对Comparator你没有什么帮助，因为标准的排序算法假设你遵守它。

除了从 Wikipedia 实现拓扑排序算法之外，您还可以查看这个库（当有人谈到有向图和拓扑排序时经常提到它）或那个实现。

于 2015-01-22T22:21:18.823 回答