有向无环图的拓扑排序

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

所以这种方法是有缺陷的！不确定它是否可以被挽救，我会离开一会儿，如果有人能发现如何修复它，要么抓住你能找到的东西并发布一个新的答案，要么编辑我的。

具体来说，我在评论中的示例中使用了下面的算法，它不会输出给出的示例，因此它显然是有缺陷的。

我学习拓扑排序的方法如下：

• 创建所有元素的列表，其中没有指向它的箭头
• 创建元素字典 -

在您的示例中，两个字典和列表如下所示：

D1      D2         List
W: 1    V: W, X    V
Y: 1    W: Y, Z
Z: 2    X: Z
X: 1

然后，启动一个循环，在每次迭代中执行以下操作：

< li >输出列表的所有元素，这些元素当前没有指向它们的箭头。制作列表的临时副本，并清除列表，为下一次迭代做准备 < li >循环遍历临时副本，并在字典中查找作为element -的每个元素(如果存在)

如果你到了这一步，带有元素的字典-

对于您的示例，每次迭代将输出以下内容:

1. V
2. W、 X（第二次迭代输出W和X）
3. Y、 Z

如果您想知道我是如何得出这个解决方案的，只需使用上面的字典和列表作为起点，一步一步地浏览我的迭代描述。

现在，具体回答您的问题，如何输出所有组合。“组合”发挥作用的唯一地方是每次迭代。基本上，您在迭代的第一步输出的所有元素（您制作了临时副本的元素）都被认为是“等效的”，并且它们之间的任何内部排序都不会对拓扑排序产生影响。

因此，请执行以下操作：

• 在迭代的第一点，将这些元素放入一个列表，并将其添加到另一个列表中，从而得到一个列表列表。
• 列表列表现在将包含每个迭代作为一个元素，一个元素将是另一个列表，其中包含该迭代中输出的元素。
• 现在，将第一个列表的所有置换与第二个列表的全部置换与第三个列表的置换组合，依此类推

这意味着获取以下输出：

第五章 < li>W，X Y，Z轴

它总共给出1*2*2=4个排列，您将第一次迭代的所有排列（即1）与第二次迭代的所有排列（即2， W， X和X， W）与第三次迭代的所有排列（即2， Y， Z和Z， Y）相结合。

作为有效拓扑排序的排列的最终列表是这样的：

1. V、W、X、Y、Z
2. V、X、W、Y、Z
3. V、W、X、Z、Y
4. V、X、W、Z、Y

以下是评论中的示例：

A和B没有边缘。A和B都有到C的边，但只有A有到D的边。C和D都没有任何出边。

其中给出：

A --> C
A --> D
B --> C

字典和列表：

D1     D2        List
C: 2   A: C, D   A
D: 1   B: C      B

迭代将输出：

1. A， B
2. D， C

所有排列 （2 * 2 = 4）：

< li>A、B、D、C < li>A、B、C、D B、A、D、C B、A、C、D

Answer 2

也许可以更快地计算排序的数量，但实际上生成我能想到的所有排序的唯一方法是使用完全的蛮力递归。（我说“蛮力”，但这仍然比测试每个可能排列的最残酷的蛮力方法好得多：））

基本上，在每一步都有一组剩余的顶点（即尚未添加到顺序中的顶点），这些顶点的子集X可以在下一步中安全添加。该子集X正是S中的顶点没有内边的顶点集。

对于给定的偏解 L，它由一些已在顺序中的顶点、剩余顶点的集合 S 和 S 中没有来自 S 中其他顶点的内边的顶点集合 X 组成，调用 Generate（L， X， S） 将生成所有以 L 开头的有效拓扑顺序。

• 如果X为空：
  • 要么L已经是一个完整的解，在这种情况下它包含所有n个顶点，而S也是空的，要么原始图包含一个循环
  • 如果S为空：
    • 输出L作为解决方案
    < li >报告存在循环。(事实上，S中的所有顶点都参与某个循环，尽管可能不止一个。)
    < li >对于X中的每个X: < ul > < li >设L '是末尾加了x的L。 < li >设X '是X\{x}加上S中顶点中唯一的边内顶点来自X的顶点。 < li >让S' = S\{x}。 < li >生成(L '，X '，S')

    首先，找出没有内边的所有顶点的集合X，并调用Generate(()，X，V)。因为在“For each”循环中选择的每个x都是不同的，所以由该循环的迭代生成的每个部分解L '也必须是不同的，所以任何对Generate()的调用(包括顶级调用)都不会多次生成解。

    在实践中，形成X'比上述伪代码建议的更有效：当我们选择X时，我们可以从X中删除所有外边缘，但也可以将它们添加到临时边缘列表中，并且通过跟踪每个顶点的内边缘总数（例如，在按顶点数索引的数组中），我们可以有效地检测哪些顶点现在有0个内边缘，因此应该添加到X'。然后在循环迭代结束时，我们删除的所有边都可以从临时列表中恢复。

Answer 3

Pruesse和Ruskey的论文“快速生成线性扩展”中给出了一种为给定DAG生成所有拓扑排序的算法（也称为生成部分顺序的所有线性扩展）。该算法具有在输出中线性的摊销运行时间（例如：如果它输出M个拓扑排序，它在时间O（M）中运行）。

请注意，一般来说，您不能真正拥有任何运行时相对于输入大小有效的内容，因为输出的大小可能比输入大得多。例如，完全断开连接的 N 个节点的 DAG 具有 N！可能的拓扑排序。