创建给定叶节点的 DAG

Question

假设我们有一个带有单个叶节点 leafN 的 DAG。每个节点都是一个包含父节点列表的对象。节点 class 可以是 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)))（为清楚起见，我忽略了每个节点的对象。）

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

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

Answer 1

您需要做的就是将您的节点放入某种数据结构中，以便您轻松找到节点。如果您的节点中的整数值是连续的（或接近它）并且从一个小数字开始，那么您可以使用一个数组并将具有整数 i 的节点放在数组的位置 i （这使得在节点中包含整数有点多余）。

这一切在这个网站上都有很好的解释（但请注意，在他们的实现中，列表是边缘到，而不是边缘）http://algs4.cs.princeton.edu/42directed/

Answer 2

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

不是 Parent ---> Child 节点关系，而是 Child ---> Parent 关系。

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

所以你最终得到

    leafD
   ↙     ↘
 leafB  leafC
   ↘     ↙
    leafA

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

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

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

查看 this question 以获取有关如何反转 DAG 的更多解决方案。

Create a DAG given leaf nodes