For循环递归函数在递归结束后继续

我在C++中的图上实现深度优先搜索。给定一个起始顶点，该算法应该执行DFS，直到找到一个目标节点（即一个goal设置为true的节点），并返回所采用的路径。我试图递归地做到这一点，这是我的代码：For循环递归函数在递归结束后继续

vector<char>* dfs(graph g, node* s){ 

    static vector<char> path; 
    s->set_visited(); 
    path.push_back(s->get_tag()); //Adds node to path 

    if(s->is_goal()){ 
     g.set_all_visited(); 
    } 

    else{ 
     for(int i=0; i<(s->get_no_edges()); i++){ 
      if(!(s->get_edge(i)->get_dest()->is_visited())) //If it is unvisited, apply recursion 
       dfs(g, s->get_edge(i)->get_dest()); 
     } 
    } 

    return &path; 
}

据我所知，所产生的路径将只列出他们由DFS访问的顺序节点，从不是一个实际的路径开始到目标节点。

问题在于，即使在找到目标节点之后，函数仍继续打印节点。为了避免这种情况，我将图g中的所有节点设置为使用set_all_visited()访问，并在继续前检查了else部分中是否访问了节点，但这似乎不起作用。当我执行干运行时，即使在找到目标节点之后，该功能仍然访问for循环中节点的所有边缘，并且我不知道如何阻止该情况发生。

来源

2017-04-05 Stefania Damato

也许它与按值传递'g'有关。尝试通过引用传递它。将所有节点标记为已访问的'g'与其他递归调用可用的'g'不同。 – IVlad

https://ericlippert.com/2014/03/05/how-to-debug-small-programs/ 特别是在这种情况下，你似乎确信它停留在for循环 - 因此'我<(s-> get_no_edges（））是真的。所以，在调试器（或者使用'穷人'调试器'cout'）看看'i'和's-> get_no_edges（）'，然后看看为什么这个条件仍然是真的。 – slim

@IVlad我试了一下，它似乎现在工作！这样愚蠢的错误。谢谢！ –

您按值传递g而不是引用。这意味着无论何时您找到一个目标节点并从递归调用返回时，该实例g仍将其节点设置为未访问。这就是重复发生的原因。

来源

2017-04-05 16:23:02

我知道你的主要问题是回答，我还是会给一些建议：

1）不要使用静态载体，你不能重用功能。你可以创建一个你期待路径的向量并传递指向该向量的指针。

2）为了确保路径中没有所有访问过的节点，可以从dfs函数返回一个bool来表示是否有到目的地的路径。您也可以避免以这种方式传递图形对象。

这些变化你的代码将变为：

bool dfs(node* s, vector<char>* path){ 

    s->set_visited(); 

    if(s->is_goal()){ 
     path.push_back(s->get_tag()); 
     return true; 
    } 

    else{ 
     for(int i=0; i<(s->get_no_edges()); i++){ 
      if(!(s->get_edge(i)->get_dest()->is_visited())) //If it is unvisited, apply recursion 
       if(dfs(s->get_edge(i)->get_dest(), path)) { 
        path.push_back(s->get_tag()); 
        return true; 
       } 
     } 
    } 

    return false; 
}

这将返回反向路径，从目的到源路径，即，存在的std ::相反。

如果你做了一个BFS，你会得到最短路径而不是一些随机路径，假设边的权重相同。

来源

2017-04-05 16:54:57

太棒了！改变它像你说的，欢呼。 –

For循环递归函数在递归结束后继续

回答

相关问题