algorithm - 有向无环图的拓扑排序

Question

如何为有向无环图输出所有可能的拓扑排序？例如，给定一个图，其中 V 指向 W 和 X，W 指向 Y 和 Z，X 指向 Z:

V --> W --> Y
      W --> Z
V --> X --> Z

您如何对该图进行拓扑排序以产生所有可能的结果？我能够使用广度优先搜索来获取 V、W、X、Y、Z，并使用深度优先搜索来获取 V、W、Y、Z、X。但无法输出任何其他类型.

Answer 1

论文 "Generating Linear Extensions Fast" by Pruesse and Ruskey 中给出了为给定 DAG 生成所有拓扑排序的算法(也称为生成偏序的所有线性扩展) .该算法的摊销运行时间与输出 呈线性关系(例如:如果它输出 M 个拓扑排序，则它的运行时间为 O(M))。

请注意，一般而言，您不可能真正拥有任何具有相对于输入大小有效的运行时的东西，因为输出的大小可能比输入的大小呈指数级增长。例如，一个完全断开连接的 N 个节点的 DAG 有 N!可能的拓扑排序。