c++ - 深度优先搜索

我有一个后缀树，这个树的每个节点都是一个结构

struct state {
int len, link;
map<char,int> next; };
state[100000] st;

我需要为每个节点创建dfs并获取所有可以访问的字符串，但我不知道如何创建。
这是我的dfs函数

 void getNext(int node){
  for(map<char,int>::iterator it = st[node].next.begin();it != st[node].next.end();it++){
      getNext(it->second);
 }
}

如果我能做些

map<int,vector<string> >

其中int是我的树和向量字符串的一个节点，我可以访问它
现在它工作了

void createSuffices(int node){//, map<int, vector<string> > &suffices) {
if (suffices[sz - 1].size() == 0 && (node == sz - 1)) {
    // node is a leaf
    // add a vector for this node containing just
    // one element: the empty string
    //suffices[node] = new vector<string>
    //suffices.add(node, new vector<string>({""}));
    vector<string> r;
    r.push_back(string());
    suffices[node] = r;
} else {
    // node is not a leaf
    // create the vector that will be built up
    vector<string> v;
    // loop over each child
    for(map<char,int>::iterator it = st[node].next.begin();it != st[node].next.end();it++){
        createSuffices(it->second);
        vector<string> t = suffices[it->second];
        for(int i = 0; i < t.size(); i ++){
            v.push_back(string(1,it->first) + t[i]);
        }
    }
    suffices[node] = v;
}
}

最佳答案

您可以将map<int, vector<string>>与深度优先搜索一起传递。当一个递归调用从某个节点返回时，您知道该节点的所有足够都准备好了。我的C++技能太有限，所以我会用伪代码编写它：

void createSuffices(int node, map<int, vector<string>> suffices) {
    if (st[node].next.empty()) {
        // node is a leaf
        // add a vector for this node containing just
        // one element: the empty string
        suffices.add(node, new vector<string>({""}));
    } else {
        // node is not a leaf
        // create the vector that will be built up
        vector<string> v;
        // loop over each child
        foreach pair<char, int> p in st[node].next {
            // handle the child
            createSuffices(p.second, suffices);

            // prepend the character to all suffices of the child
            foreach string suffix in suffices(p.second) {
                v.add(concatenate(p.first, suffix));
            }
        }
        // add the created vector to the suffix map
        suffices.add(node, v);
    }
}

关于c++ - 深度优先搜索，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/19220332/