使用多个源线性化 DAG

Question

我正在看我的算法书，我发现有一个简单的算法可以通过逐个删除源节点来线性化单个源有向无环图。有人能给我举个例子来说明为什么这不适用于多个来源吗？

Answer 1

是的，您可以使用源删除算法对由任意数量的不同组件组成的广义 DAG 进行拓扑排序，这些组件是简单的 DAG。

证明并不难。你应该亲自尝试一下。如果你看不懂，请询问，我会给出一个大纲。

但是有一种更简单的方法来进行拓扑排序。将新的主源节点连接到具有单边的所有 DAG 源，然后从主源进行深度优先搜索，按后序应用节点编号（即，在访问其所有后代之后，对每个节点连续编号）。主源获得最高编号。忽略这个。剩余的节点号以相反的顺序进行拓扑排序。 即不需要像源删除算法那样解构图。

Answer 2

单源 DAG 只是一个有向森林。您可以将其线性化，例如通过

预序遍历

，就像一棵树一样，从每个根开始依次进行。 例如这张图：

变成

(a (b c)) (e f g)

。

一般 DAG 的问题是你可能必须多次重复同一个节点：

会变成

(a (b c)) (e (b c) f g)

，然后当你重建图时，你可能会得到：

除非你专门处理重复项。不过，您可以线性化为

(a (b c)) (e b f g)

并通过记住已经重建的节点来解决问题。

无论如何，我想使用你的节点删除算法，你会在第一次遇到时删除这里的

b

，这样你就无法从

e

到达它，并且你只会得到

(a (b c)) (e f g)

错了。

Answer 3