Рекурсивный алгоритм первого поиска глубины (DFS) в C++

Я реализовал граф в классе 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, в противном случае он обычно выходит без ошибок

1 2
c++ algorithm recursion depth-first-search

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 из параметров и операторов, связанных с ней. Возвращаемое значение является достаточным.

EDIT: проблема была в этой строке кода 

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

Здесь функция возвращалась, даже если цель не была найдена. Так что оставшиеся (в очереди) соседи не посещались. Исправление делает функцию возвращаемой только в том случае, если цель достигнута. В исправлении также есть оператор "return -1" в конце функции, который указывает, что функция завершилась, не достигнув цели.

Для оценки логики кода, памяти и читабельности, а также предложений по лучшим практикам вы можете разместить свой код здесь: https://codereview.stackexchange.com/

1