Как построить дерево DFS, если я генерирую частый образец в методе DFS?

Question

В моем алгоритме я буду создавать частые шаблоны по методу DFS, например, я генерирую по порядку A-A, A-A-B, A-A-B-C, ... *, B, C являются узлами, а - означает, что существует грань между двумя узлами.) Если не существует частых подграфов, состоящих из A-A, мы начинаем генерировать A-B, A-B-B, .... Я хочу использовать дерево DFS для хранения этих частых шаблонов. Но я не знаю, какой метод самый лучший.

Проблема, с которой я сталкиваюсь, заключается в том, должен ли я использовать указатель * prev для записи шаблона на предыдущем уровне?

// When i generate one frequent pattern, i will call `report` 
void report (Projected &projected, unsigned int sup)
{
    // i want to store this pattern in a DFS tree which implement with GPattern
}

struct GPattern {
    CODE code;
    Project project;
    vector<GPattern> children; // record all children of this pattern

    // should i use a `prev` pointer to record ancestor?
};

Answer 1

Вы строите график из GPattern объектов вручную.Вам, вероятно, лучше использовать для этого Boost::Graph, поскольку он поставляется с множеством полезных алгоритмов.

Answer 2

Я думаю, вы должны использовать дерево префиксов. посмотрите здесь