This post will cover the difference between the Depth–first search (DFS) and Breadth–first search (BFS) algorithm used to traverse/search tree or graph data structure.

1. Definition

The Depth–first search (DFS) algorithm starts at the root of the tree (or some arbitrary node for a graph) and explored as far as possible along each branch before backtracking.

 
The Breadth–first search (BFS) algorithm also starts at the root of the tree (or some arbitrary node of a graph), but unlike DFS, it explores the neighbor nodes first, before moving to the next-level neighbors. In other words, BFS explores vertices in the order of their distance from the source vertex, where distance is the minimum length of a path from the source vertex to the node.

2. Examples

The following graph shows the order in which the nodes are discovered in DFS:

DFS Tree

 
The following graph shows the order in which the nodes are discovered in BFS:

Breadth first search (BFS) tree

3. Application

Below are the applications of DFS:

Below are the applications of BFS:

  • Copying garbage collection, Cheney’s algorithm.
  • Finding the shortest path between two nodes u and v, with path length measured by the number of edges (an advantage over depth–first search).
  • Testing a graph for bipartiteness.
  • Minimum Spanning Tree for unweighted graph.
  • Web crawler.
  • Finding nodes in any connected component of a graph.
  • Ford–Fulkerson method for computing the maximum flow in a flow network.
  • Serialization/Deserialization of a binary tree.

4. DFS and BFS for Trees

We may traverse trees in multiple ways in depth–first order or breadth–first order. The depth–first search for trees can be implemented using preorder, inorder, and postorder, while the breadth–first search for trees can be implemented using level order traversal.

Beyond these basic traversals, various more complex or hybrid schemes are possible, such as depth-limited searches like iterative deepening depth–first search.

5. Implementation Details

In BFS, we need to maintain a separate data structure for tracking the tree/graph nodes yet to be visited. This is easily done iteratively using the queue data structure.

In contrast to BFS, DFS doesn’t need any additional data structure to store the tree/graph nodes. The recursive implementation of DFS uses the call stack.

6. Time Complexity

The time complexity of both DFS and BFS traversal is O(V + E), where V and E are the total number of vertices and edges in the graph, respectively.

Please note that E may vary between O(1) and O(V2), depending on how dense the graph is.

7. Memory Requirements

The memory is taken by DFS/BFS heavily depends on the structure of our tree/graph. The maximum memory taken by DFS (i.e., by call stack) is equal to the depth of the tree, and the maximum memory taken by BFS is equal to the width of the tree.

8. When to use DFS and BFS?

If we know the solution lies somewhere deep in a tree or far from the source vertex in the graph, use DFS. If we know the solution is not that far from the source vertex, use BFS.

If our tree is broad, use DFS as BFS will take too much memory. Similarly, if our tree is very deep, choose BFS over DFS.
 

 
Also See:

Depth First Search (DFS) – Interview Questions & Practice Problems

Breadth First Search (BFS) – Interview Questions & Practice Problems