algorithm - 将元组转换为树

Question

我有一个由 (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

排名不分先后。

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

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

Answer 1

我不清楚您是否在寻找指针数据结构。看来您正在寻找的是最后您应​​该能够列出节点的所有子节点。如果这是要求，您可以做的是创建一个哈希表(根据您的示例，从字符串到字符串)。然后在您的文件 readline 循环中将父级设置为哈希表中的键，并将字符串向量设置为相应的值。将 child 推到这个向量上。在 C++ 中，它将如下所示

#include <hash_map>
#include <vector>
#include <string>
using namespace std;
hash_map<string, vector<string>* > graph;
string parent, child;

然后在文件readline循环中

cin >> parent >> child >> child;
if ( graph[parent] == graph.end() ) {
    graph[parent] = new vector<string>();
}
graph[parent]->push_back(child);

记得在完成后删除向量，或使用 auto_ptr。

在伪代码中:

for every tuple:
    create HashTable entry with key = tuple.parent
    HashTable[tuple.parent].addToList(tuple.child)