java - 仅当特定对象具有可比较性时设置排序

Question

我有一组独特的数据。假设它看起来像这样:

0: domainA.org -> domainB.org
1: domainY.org -> domainZ.org
2: domainB.org -> domainC.org
3: domainD.org -> domainE.org
4: domainX.org -> domainY.org
5: domainC.org -> domainD.org

为了将 domainA.org 相关数据复制到 B C D 和 E，将 doimanY.org 相关数据复制到 X 和 Z，我需要在下面迭代该集合订单:

0: domainA.org -> domainB.org
2: domainB.org -> domainC.org
5: domainC.org -> domainD.org
3: domainD.org -> domainE.org

4: domainX.org -> domainY.org
1: domainY.org -> domainZ.org

在 A -> B -> C -> D -> E 之前处理 X -> Y -> Z 并不重要，但它们不会彼此相关。

对每个“类别”进行排序，例如数据的每个独立部分本身都相当容易。 我为 sourceDomain -> destinationDomain 制作了包装器对象，实现 Comparable 并使用 SortedSet 为我进行排序。 现在问题来了。
这就是我的 comparteTo 实现的样子:

if (source.equals(other.destination)) {
    return 1;
} else if (destination.equals(other.source)) {
    return -1;
}
return 0;

它只能比较最终列表中彼此相邻的 2 个对象，否则它将其他对象“视为”相同。
(更不用说如果compareTo在某个时刻返回0，TreeSet不会向自身添加项目) 因此，它没有正确对示例 1 中显示的数据进行排序。
我的想法是迭代源集并添加将条目与其他条目进行比较并创建单独的集，一旦完成排序我就可以将它们连接在一起。
其复杂度至少为 n^2，这非常糟糕。
我的问题:我们能做得更好吗？

Answer 1

您正在寻找的是图中的拓扑排序。有多种算法可以解决这个问题，可以在 the Wikipedia article 上找到伪代码。 .

最容易实现的是深度优先搜索，复制如下:

L ← Empty list that will contain the sorted nodes
foreach node n do
    if not marked n then visit(n) 

function visit(node n)
    if n has a temporary mark then stop (cyclic dependency found!)
    if n is not marked (i.e. has not been visited yet) then
        mark n temporarily
    for each node m with an edge from n to m do
        visit(m)
        mark n permanently
        unmark n temporarily
        add n to head of L

这最多具有 O(节点 + 边) 的时间复杂度，在您的情况下，节点 = 边，因此这足够快。