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

Question

I've implemented the graph in the class Graph as adjacency matrix with all required functions to access and modify it, the ones i needed in the DFS algorithm

// 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)

now i tried to implement a recursive DFS but it always stuck at some point, it never recurse back after it calls itself again, so it works and finds the goal if it exists on its path before it reaches a leaf node, but then it stops after reaching a leaf node

It keeps track of the nodes by indicating colors, unvisited node is WHITE, node in progress is GREY, node that is done (visited and all children are visited) is BLACK.

Here's the kickoff function:

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

and here's the visit function:

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

Tested it on this graph:

enter image description here

It only finds the goal if it was within A, B, or D, otherwise it exits normally without errors

FYI, in case of tree, it's meaningless to check whether the node was visited or not, since there are no back edges. — mangusta
As soon as you find an unvisited node you return the result of searching through that node, not considering any other children. You need to check if the recursive search was successful. — molbdnilo
Sorry, it's graph, there could be cycles, just to avoid loops, and about finding the goal that's what the flag goal_f do, when it's raised each instance of the function which all supposed to be within the while loop will get out of it to exit and won't do more search — M.Allam

Serge Rogatch Serge Rogatch · Accepted Answer · 2015-06-26T10:16:23

The following change to your code should help:

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

You can further remove goal_f variable from parameters and statements involving it. A return value is sufficient.

EDIT: the problem was in this line of code

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

Here the function was returning even if the goal had not been found. So the remaining (in the queue) neighbors were not getting visited. The fix makes the function to return only if the goal has been reached. In the fix, there is also "return -1" statement in the end of the function, which indicates that the function finished without reaching the goal.

For assesment of code logic, memory, and readability, and suggestions of best practices you can post your code here: https://codereview.stackexchange.com/

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

1 Answers