преобразовать кортежи в дерево

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 loop установите родителя в качестве ключа в хеш-таблице и вектора строк в качестве соответствующего значения.Нажмите ребенка на этот вектор.В C ++ это будет выглядеть следующим образом:

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

Затем в цикле чтения файла

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)

Answer 2

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

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

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

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

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

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