CODEWITHSUNDEEP
c++algorithmrecursiondepth-first-search
M.Allam
M.Allam

Reputation: 25

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

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

Upvotes: 2

Views: 6055

Answers (1)

Serge Rogatch
Serge Rogatch

Reputation: 15040

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/

Upvotes: 1

Related Questions