C++ 中的递归深度优先搜索 (DFS) 算法

Question

我已经将 class Graph 中的图形实现为邻接矩阵，其中包含访问和修改它所需的所有函数，这些是我在 DFS 算法中需要的

// for a Graph x, node v
string x.get_node_value(v)  //returns the the label of the node
queue x.neighbors(v) //returns a queue with the adjacent nodes to the node v (nodes index on the graph starts from 1)

现在我尝试实现递归 DFS，但它总是停留在某个点，它在再次调用自身后永远不会递归，所以它可以工作并找到目标，如果它在到达叶节点之前存在于其路径上，但在到达叶节点后停止

它通过指示颜色来跟踪节点，未访问的节点为白色，进行中的节点为灰色，完成的节点（已访问和所有子节点都被访问）为黑色。

这是启动函数：

int Search::DFSr(const std::string search_key, Graph& x, int starting_node){
    Color * visited_nodes = new Color[x.size()];
    for(int i=0; i<x.size(); i++){visited_nodes[i] = WHITE;}
    bool goal_f = 0;
    int goal = DFSUtil(search_key, x, starting_node, visited_nodes, goal_f);
    if(goal_f) return goal;
    else return -1;
}

这是访问函数：

int Search::DFSUtil(std::string search_key, Graph& x, int current_node, Color(visited_nodes)[], bool& goal_f){
    visited_nodes[current_node-1] = GREY; //-1 because array index start from 0 but nodes index on the graph starts from 1
    if(x.get_node_value(current_node) == search_key ){
        goal_f = 1;
        return current_node;
    }
    else{
        std::queue <int> childs =  x.neighbors(current_node);
        while(!childs.empty() && !goal_f){
            if(visited_nodes[childs.front()-1] == WHITE){
                return DFSUtil(search_key, x, childs.front(), visited_nodes, goal_f);
            }
            childs.pop();
        }
        visited_nodes[current_node-1] = BLACK;
    }
}

在这张图上测试过：

只有在A、B、D范围内才能找到目标，否则正常退出

Answer 1

对您的代码进行以下更改应该会有所帮助：

int Search::DFSUtil(std::string search_key, Graph& x, int current_node, Color(visited_nodes)[], bool& goal_f){
    visited_nodes[current_node-1] = GREY; //-1 because array index start from 0 but nodes index on the graph starts from 1
    if(x.get_node_value(current_node) == search_key ){
        goal_f = 1;
        return current_node;
    }
    else{
        std::queue <int> childs =  x.neighbors(current_node);
        while(!childs.empty() && !goal_f){
            if(visited_nodes[childs.front()-1] == WHITE){
                int result = DFSUtil(search_key, x, childs.front(), visited_nodes, goal_f);
                if( result >= 0 ) {
                    return result;
                }
            }
            childs.pop();
        }
        visited_nodes[current_node-1] = BLACK;
    }
    return -1;
}

您可以进一步从涉及它的参数和语句中删除 goal_f 变量。 return 值就足够了。

编辑：问题出在这行代码中

return DFSUtil(search_key, x, childs.front(), visited_nodes, goal_f);

这里的函数正在 returning，即使没有找到目标。所以剩下的（在队列中）邻居没有被访问。仅当已达到目标时，此修复程序才使函数变为 return。在修复中，函数末尾也有"return -1"语句，表示函数没有达到目标就结束了。

要评估代码逻辑、内存和可读性，以及最佳实践建议，您可以在此处post 您的代码：https://codereview.stackexchange.com/

C++ 中的递归深度优先搜索 (DFS) 算法

Recursive Depth First Search (DFS) algorithm in C++

c++

algorithm

recursion

depth-first-search