algorithm - 创建给定叶节点的 DAG

Question

假设我们有一个带有单个叶节点 leafN 的 DAG。每个节点都是一个包含父节点列表的对象。节点类可以类似于 class Node(Object, List[Node]。

如何从leafN构建DAG？

例如，给定具有两个父节点的叶节点 leafD，leafD(Object@123, List(leafC(leafA(null)), leafB(leafA(null)))) 它的 DAG 将是:

    leafA
   /     \
 leafB  leafC
    \    /
    leafD

即 leafA(leafB(leafD(null)), leafC(leafD(null)))(为清楚起见，我忽略了每个节点的对象。)

简而言之，我们有一个带有父指针的叶节点，它本身也有父指针，最后，在应用算法之后，我们想要一个带有指向子节点的指针的根节点，子节点进一步有指向子节点的指针.

不需要代码，算法或任何链接就足够了。

Answer 1

这很简单，只要您意识到理论上只有 DAG 中的边方向发生了变化。

您有一个Child ---> Parent 关系，而不是Parent ---> Child 节点关系。

因此，您需要做的就是根据给定的关系构造一个 DAG，假设子节点实际上是父节点，而父节点是子节点。

所以你最终得到

    leafD
   ↙     ↘
 leafB  leafC
   ↘     ↙
    leafA

现在，您需要做的就是反转 DAG 中的边。

这很简单，一种方法是遍历 DAG，获取所有边关系，然后将它们一一反转。

另一种方法是使用层序遍历递归地执行此操作。

检查 this question有关如何反转 DAG 的更多解决方案。