title: Finding minimum hops to a node in a graph - BFS or DFS?
body: <p>Is it safe to say that in a problem where you're asked to find the minimum number of hops to reach a particular node in a graph, BFS is better than DFS?</p>
  
  <p>I understand, in a search problem, where the task is to search a node, BFS or DFS being better would depend on the nature of the graph. For example, if your graph is a family tree, and you're looking for someone alive, it would be better to use DFS, since the node is more likely to be deep in the graph. Conversely, if you're looking for someone who passed away many years back, BFS would be ideal.</p>
  
  <p>However, in this case, I feel that, even if DFS were to find the node very quickly, it would still need to backtrack, and find all other paths that reach to the destination, and then compare among them to find the path with the least number of hops. For BFS, on the other hand, the first time you find a node, you can conclude that, this is indeed the path with the least number of hops.</p>
  
  <p>My question is</p>
  
  <ol>
  <li><strong>Is it safe to say, in case of searching a 'key' node, the choice between BFS or DFS
  depends on the nature of the graph, but in finding minimum number of hops to reach a
  destination node, BFS is better ?</strong></li>
  <li><strong>What is the time complexity of finding the minimum number of hops to
  reach a destination node in case of BFS and DFS. For BFS, I think it
  would O(V+E). What is the time complexity in case of DFS ? Would it be exponential, that is V^V, since it's possible for a node to be connected to all other nodes, including itself</strong></li>
  </ol>
  
  <p>My code using DFS</p>
  
  <pre><code>/* Depth First Search */
  public int DFSrecursive(Vertex source, Vertex destination)
  {
      if(source == destination)
      {
          source.visited = false;
          return 0;
      }
  
  
      int min = Integer.MAX_VALUE-1;
      for(int i = 0;i&lt;source.neighbors.size();i++)
      {
          Vertex neighbor = source.neighbors.get( i );
          if(neighbor.visited == false)
          {
              neighbor.visited = true;
              min = Math.min( min, DFSrecursive( neighbor, destination )+1 );
          }
      }
  
      source.visited = false;
      return min;
  }
  </code></pre>
  
  <p>My code using BFS</p>
  
  <pre><code>/* Breadth First Search */
      public int distBFSHashtable(Vertex source, Vertex destination)
      {
          /* Everything in the queue will be unique, because if, already visited, I don't push into queue.
           * Also, at the time of pushing itself, I made it's visited to be true */
          Queue&lt;Vertex&gt; toprocess = new LinkedList&lt;&gt;();
  
          toprocess.add( source );
          source.visited = true;
  
          /* This table gives the distance of each vertex from source */
          Hashtable&lt;Vertex, Integer&gt; distanceTable = new Hashtable&lt;&gt;();
          distanceTable.put( source, 0 );
  
          while(toprocess.size() &gt; 0 )
          {
              Vertex current = toprocess.poll();
  
              for(int i = 0;i&lt;current.neighbors.size();i++)
              {
                  Vertex neighbor = current.neighbors.get( i );
  //                distanceTable.put( neighbor, distanceTable.get( current )+1 );
  
                  if(neighbor.visited == false)
                  {
                      neighbor.visited = true;
                      toprocess.add( neighbor );
                      distanceTable.put( neighbor, distanceTable.get( current )+1 );
                  }
  
                  if(neighbor == destination)
                      return distanceTable.get( neighbor );
              }
          }
          return -1;
      }
  </code></pre>