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

Question

我有一组项目和一个定义部分排序的比较器函数 - 给定两个项目，它返回“=”、“<”、“>”或“未定义排序”(例如“<>”) )。我想生成一个尊重此部分排序的项目排序列表。

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

我想过尝试使用经典排序算法并将“<>”视为“=”，但它不起作用，因为我可能会出现 A < B, A <> C, B <> C 的情况，所以我不能将 C 视为等于 A 和 B。

有什么想法或指示吗？

Answer 1

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

设S为要排序的元素集合，其中有partial order在S中。令 used 为字典，将 S 中的每个元素映射到 bool 值(默认为 false)，该值将为 true 当我们访问带有此元素的“节点”时。令 stack 为来自 S 的元素堆栈(默认为空)。

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

• 将used[x]设置为true

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

  • 如果 used[y] 为 false 并且 x 小于或等于 y (*):

    • 调用dfs(y)

• 将x添加到堆栈

然后:

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

  • 如果used[x]为false:

    • 调用dfs(x)

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

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

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