c++ - 如果我在 DFS 方法中生成频繁模式，如何构建 DFS 树？

Question

在我的算法中，我将通过 DFS 方法创建频繁模式，例如，我生成 A-A, A-A-B, A-A-B-C, .. .顺序。(这三种模式为频繁子图模式，A,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

我认为你应该使用前缀树。看看here