基于比较器(而不是图)的拓扑排序

Question

我有一组项和一个比较器函数，它定义了一个偏序--给定两个项，它返回"=“、"<”、">“或”没有定义的排序“(例如"<>")。我想要产生一个排序列表的项目，尊重这种偏序。

如果我寻找算法来进行拓扑排序，它们通常以有向无圈图开始。但是我没有DAG，而且我看不到一种简单的方法来构造DAG而不做大量的运算(可能是N*N？)比较。我想要的是一种类似于快速排序的算法，它通过比较和交换列表中选定的项目来工作。有这样的算法吗？我假设大多数经典的排序算法都会因为不确定性而失败。

我想尝试使用一个经典的排序算法，把" <>“当作"="，但是它不起作用，因为我可以在A< B，A <> C，B <>C的情况下，所以我不能把C看作等于A和B。

有什么想法或建议吗？

Answer 1

不需要显式地创建图来使用拓扑排序算法。

让S是您想要排序的元素集合，S中有一个偏序。假设used是将每个元素从S映射到布尔值(默认情况下是false)的字典，当我们使用该元素访问“节点”时，该值将是true。将stack设为来自S的元素堆栈(默认为空)。

定义一个方法dfs(x) (x是S的一个元素)，它执行以下操作：

• 将used[x]设置为true
• 对于S中的每个元素S

- If `used[y]` is `false` and `x` is less than or equal to `y` (\*):

    - Call `dfs(y)`

​

​

• 将x添加到stack

然后：

• 对于S中的每个元素S

- If `used[x]` is `false`:

    - Call `dfs(x)`

​

​

在这个循环之后，stack中的元素将被排序(从stack中弹出的第一项是最小项(不一定最小)，最后一项是最大项(不一定是最大值))。

这个算法显然在O(n^2)中运行，因为它仍然是一个拓扑排序，只是没有显式地创建图。

(*)：就像拓扑排序只处理从x到y的边，而不处理边从y到x或者根本没有边的情况，该算法只处理“小于或等于”关系。