title: Recursive Depth First Search (DFS) algorithm in C++
body: <p>I've implemented the graph in the class <code>Graph</code> as adjacency matrix with all required functions to access and modify it, the ones i needed in the DFS algorithm</p>
  
  <pre><code>// 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)
  </code></pre>
  
  <p>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</p>
  
  <p>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.</p>
  
  <p>Here's the kickoff function:</p>
  
  <pre><code>int Search::DFSr(const std::string search_key, Graph&amp; x, int starting_node){
      Color * visited_nodes = new Color[x.size()];
      for(int i=0; i&lt;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;
  }
  </code></pre>
  
  <p>and here's the visit function:</p>
  
  <pre><code>int Search::DFSUtil(std::string search_key, Graph&amp; x, int current_node, Color(visited_nodes)[], bool&amp; 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 &lt;int&gt; childs =  x.neighbors(current_node);
          while(!childs.empty() &amp;&amp; !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;
      }
  }
  </code></pre>
  
  <p>Tested it on this graph:</p>
  
  <p><img src="https://i.stack.imgur.com/lFbiz.png" alt="enter image description here"></p>
  
  <p>It only finds the goal if it was within A, B, or D, otherwise it exits normally without errors</p>