首页 文章

C中的递归深度优先搜索（DFS）算法

提问于
浏览 次
2

我已经在类 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，但它总是停留在某个点上，它再也不会在它再次调用自己后回复，所以它工作并找到目标，如果它到达叶子节点之前它的路径上存在，但它然后停止到达叶节点后

它通过指示颜色跟踪节点，未访问的节点是WHITE，正在进行的节点是GRAY，完成的节点（访问并且所有访问的子节点）是黑色的 .

这是启动功能：

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;
    }
}

在此图表上测试过：

enter image description here

它只能找到目标，如果它在A，B或D范围内，否则它会正常退出而没有错误

c++ algorithm recursion depth-first-search

1 回答

  • 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 DFSUtil(search_key, x, childs.front(), visited_nodes, goal_f);

    即使未找到目标，此功能也会返回 . 所以剩下的（在队列中）邻居没有被访问 . 修复程序仅在达到目标时才返回函数 . 在修复中，函数末尾还有“return -1”语句，表示函数在没有达到目标的情况下完成 .

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

    回复于

相关问题