基于比较器（而不是图）的拓扑排序

Question

我有一组项目和一个比较器函数，它定义了部分排序——给定两个项目，它返回“=”、“<”、“>”或“没有定义的排序”（比如“<>”）。我想生成一个尊重这种部分排序的项目的排序列表。

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

我想尝试使用经典的排序算法并将“<>”视为“=”，但它不起作用，因为我可以遇到 A < B、A <> C、B <> C，所以我可以'不要将 C 视为等于 A 和 B。

任何想法或指示？

Answer 1

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

让S是要排序的元素集，并且中有偏序S。让成为将每个元素映射到布尔值（默认情况下）used的字典，当我们使用该元素访问“节点”时，该布尔值将是该值。让为元素堆栈（默认为空）。SfalsetruestackS

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

• 设置used[x]​true

• y对于中的每个元素S：

  • 如果used[y]是false且x小于或等于y(*)：

    • 称呼dfs(y)

• 添加x​stack

然后：

• x对于中的每个元素S：

  • 如果used[x]是false：

    • 称呼dfs(x)

在此循环之后， in 中的元素stack将被排序（要弹出的第一个项目stack是最小的（不一定是最小的），最后一个项目是最大的（不一定是最大的））。

该算法显然运行时间为 O(n^2)，因为它仍然是拓扑排序，只是没有显式创建图。

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