[algorithm] Breadth First Vs Depth First

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.

Hopefully that should be enough for understanding the Breadth-First and Depth-First searches. For further reading I would recommend the Graphs chapter from an excellent data structures book by Robert Lafore.