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.

Understanding Breadth and Depth


Depth-First Search:

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:

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.

 

BFS

DFS

BFS Stands for “Breadth First Search”. DFS stands for “Depth First Search”.
 BFS starts traversal from the root node and then explore the search in the level by level manner i.e. as close as possible from the root node.  DFS starts the traversal from the root node and explore the search as far as possible from the root node i.e. depth wise.
Breadth First Search can be done with the help of queue i.e. FIFOimplementation. Depth First Search can be done with the help of Stack i.e. LIFOimplementations.
This algorithm works in single stage. The visited vertices are removed from the queue and then displayed at once. This algorithm works in two stages – in the first stage the visited vertices are pushed onto the stack and later on when there is no vertex further to visit those are popped-off.
BFS is slower than DFS. DFS is more faster than BFS.

BFS requires more memory compare to DFS.

 public void BFS(Digraph G)
   {
      // BFS uses Queue data structure
      Queue q = new LinkedList();   
      for (i = 0; i < marked.length; i++)
         marked[i] = false;     
      q.add(0);                    
          
      while(!q.isEmpty())
      {  int nextNode;             
         nextNode = q.remove();
	 int[] adj = G.adj(nextNode);
         if (!marked[nextNode])
         { marked[nextNode] = true>;   
            for (int i = 0; i < NNodes; i++ )
               if (adj[i] > 0 && ! marked[i])
                  q.add(i);
         }
      }
   }

DFS require less memory compare to BFS.

private void dfs(Digraph G, int v){ 
	marked[v] = true;
	for (Object w : G.adj(v)) {
		int we = (Integer) w;
			if (!marked[we])
				dfs(G, we);
	}
	post.add(v);
}
Applications of BFS
> To find Shortest path
> Single Source & All pairs shortest paths
> In Spanning tree
> In Connectivity
Applications of DFS
> Useful in Cycle detection
> In Connectivity testing
> Finding a path between V and W in the graph.
> useful in finding spanning trees & forest.
BFS is useful in finding shortest path.BFS can be used to find the shortest distance between some starting node and the remaining nodes of the graph. DFS in not so useful in finding shortest path. It is used to perform a traversal of a general graph and the idea of DFS is to make a path as long as possible, and then go back (backtrack) to add branches also as long as possible.
Example :BFS traversal Example :
DFS Traversal

used to perform a traversal of a general graph.

The idea of DFS is to make a path as long as possible, and then go back (backtrack) to add branches also as long as possible.