BFS vs DFS

This comes as a little late answer but I would love to share some useful points on this topic:

Understanding the terms:

This picture should give you the idea about the context in which the words breadth and depth are used.

Depth-First Search:

• Depth-first search algorithm acts as if it wants to get as far away from the starting point as quickly as possible.

• It generally uses a Stack to remember where it should go when it reaches a dead end.

• Rules to follow: Push first vertex A on to the Stack

  1. If possible, visit an adjacent unvisited vertex, mark it as visited, and push it on the stack.
  2. If you can’t follow Rule 1, then, if possible, pop a vertex off the stack.
  3. If you can’t follow Rule 1 or Rule 2, you’re done.

• Java code:

  public void searchDepthFirst() {
      // Begin at vertex 0 (A)
      vertexList[0].wasVisited = true;
      displayVertex(0);
      stack.push(0);
      while (!stack.isEmpty()) {
          int adjacentVertex = getAdjacentUnvisitedVertex(stack.peek());
          // If no such vertex
          if (adjacentVertex == -1) {
              stack.pop();
          } else {
              vertexList[adjacentVertex].wasVisited = true;
              // Do something
              stack.push(adjacentVertex);
          }
      }
      // Stack is empty, so we're done, reset flags
      for (int j = 0; j < nVerts; j++)
          vertexList[j].wasVisited = false;
  }
  

• Applications: Depth-first searches are often used in simulations of games (and game-like situations in the real world). In a typical game you can choose one of several possible actions. Each choice leads to further choices, each of which leads to further choices, and so on into an ever-expanding tree-shaped graph of possibilities.

Breadth-First Search:

• The breadth-first search algorithm likes to stay as close as possible to the starting point.
• This kind of search is generally implemented using a Queue.
• Rules to follow: Make starting Vertex A the current vertex
  1. Visit the next unvisited vertex (if there is one) that’s adjacent to the current vertex, mark it, and insert it into the queue.
  2. If you can’t carry out Rule 1 because there are no more unvisited vertices, remove a vertex from the queue (if possible) and make it the current vertex.
  3. If you can’t carry out Rule 2 because the queue is empty, you’re done.

• Java code:

  public void searchBreadthFirst() {
      vertexList[0].wasVisited = true;
      displayVertex(0);
      queue.insert(0);
      int v2;
      while (!queue.isEmpty()) {
          int v1 = queue.remove();
          // Until it has no unvisited neighbors, get one
          while ((v2 = getAdjUnvisitedVertex(v1)) != -1) {
              vertexList[v2].wasVisited = true;
              // Do something
              queue.insert(v2);
          }
      }
      // Queue is empty, so we're done, reset flags
      for (int j = 0; j < nVerts; j++) 
          vertexList[j].wasVisited = false;
  }
  

• Applications: Breadth-first search first finds all the vertices that are one edge away from the starting point, then all the vertices that are two edges away, and so on. This is useful if you’re trying to find the shortest path from the starting vertex to a given vertex.

   

  The difference between the two traversal orders lies in the choice of Container.

• For depth first use a stack. (The recursive implementation uses the call-stack...)
• For breadth-first use a queue.

Comparing BFS and DFS, the big advantage of DFS is that it has much lower memory requirements than BFS, because it’s not necessary to store all of the child pointers at each level. Depending on the data and what you are looking for, either DFS or BFS could be advantageous.

For example, given a family tree if one were looking for someone on the tree who’s still alive, then it would be safe to assume that person would be on the bottom of the tree. This means that a BFS would take a very long time to reach that last level. A DFS, however, would find the goal faster. But, if one were looking for a family member who died a very long time ago, then that person would be closer to the top of the tree. Then, a BFS would usually be faster than a DFS. So, the advantages of either vary depending on the data and what you’re looking for.