我正在看我的算法书，我看到有一个简单的算法线性化一个单一的源，有向无环图删除源节点一个接一个。有人能给我举个例子说明为什么这不适用于多个来源吗？
最佳答案
我假设“线性化”是指通过一对一映射将图转换成一系列节点，这样就可以恢复整个图。
单一源DAG只是一个定向林。例如，您可以将其线性化，就像树一样，从每个根按顺序开始。
例如，此图：
pre-order traversal
变成(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)，这是错误的。