Преобразование кортежей в дерево

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 

в произвольном порядке.

Имея только эти кортежи, мы можем реконструировать дерево в структуре, как:

Node (имя: String, дети: List)?

Answer 1

Выполните глубину первого обхода начиная с корневого каталога, что позволяет узлам посещать несколько раз (график должен быть ациклическим, конечно, для этого прекратить). Для каждого узла графа, который вы посещаете, вы создаете соответствующий узел дерева и соединяете его с соответствующим деревом узла его родительского графа (edit: Фактически, узел графа может соответствовать нескольким узлам дерева, вас интересует последний).

Например, скажем, ваш корень A:

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

Вы посещаете A, создать tA. Проход идет к B, вы создаете tB, подключите его к tA. Затем вы посетите «D», создать tD, подключить его к tB, то вернуться назад и посетить «C», создать tC и подключить его к tA, так что вы получите это дерево:

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

Обратите внимание, что вы можете получить экспоненциально большее дерево по сравнению с графиком таким преобразованием.

Answer 2

Мне было непонятно, если вы искали структуру данных указателя или нет. Кажется, что вы ищете, так это то, что в конце вы должны иметь возможность перечислять все дочерние узлы узла. Если это требование, то вы можете создать хэш-таблицу (в соответствии с вашим примером, от строки до строки). Затем в вашем файле readline loop задает родительский ключ в хеш-таблице и вектор строк как соответствующее значение. Нажмите на этот вектор. В 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); 

Remember удалить векторы, как только вы сделали, или использовать auto_ptr.

В псевдокоде:

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