algorithm - 将元组转换为树

我有一个由 (Parent1 -> Child1), (Parent2 -> Child2), ...., (ParentN -> ChildN) 元组描述的有向无环图(树)。是否有任何算法可以根据这些信息重建树(图)？

一个更好的例子:

Root
  Parent1
     Node1
       Child1
       Child2
  Parent2
     Node1
       Child1
       Child2

作为输入，我只有:

Root -> Parent1
Node1 -> Child1
Root -> Parent2
Parent1 -> Node1
Parent2 -> Node1
Node1 -> Child2

没有特别的顺序。

只有这些元组，我们可以在如下结构中重建树:

节点(名称:字符串， child :列表)？

最佳答案

从根开始执行深度优先遍历，允许多次访问节点(当然，图必须是非循环的才能终止)。对于你访问的每一个图节点，你创建一个对应的树节点，并将其连接到其父图节点对应的树节点( 编辑: 其实，一个图节点可以对应多个树节点，你有兴趣最后)。

例如，假设您的根是 A :

    A
   / \
  /   \
 B     C
  \   /
   \ /
    D

您访问 A ，创建 tA 。遍历到 B，您创建 tB ，将其连接到 tA 。然后访问 'D'，创建 tD ，将其连接到 tB ，然后回溯并访问 'C'，创建 tC 并将其连接到 tA ，这样你就得到了这棵树:

    tA
   / \
  /   \
 tB   tC
 |    |
 |    |
 tD   tD'

请注意，通过这种转换，与图相比，您可能会得到一个指数级更大的树。

关于algorithm - 将元组转换为树，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/4045997/