Breadth First vs Depth First Search

Search algorithms are something that I have not had to consider much when building full stack applications, but they are an important component of programming as they are frequently discussed in interviews. I am going to run through the differences between depth first and breadth first search and discuss when each is optimally used.

BFS

BFS stands for breadth first search. This method of search finds the shortest path to the target value, but is typically slower than depth first search. BFS utilizes a queue data structure to store values visited. It follows a 'first in first out' method and travels to each adjacent value before moving deeper. To demonstrate, I've created a sample "tree". A BFS search of the following tree will visit the nodes in alphabetical order:

      A
    /   \
   B     C
  / \   / \
 D   E F   G

DFS

DFS stands for depth first search. This method of search examines each value in a branch then moves to an adjacent branch. DFS utilizes a stack data structure to store values visited. After each value in a branch has been visited, all values are popped from the stack before moving to an adjacent branch. As with the example above, a DFS search of the following tree will visit the nodes in alphabetical order:

      A
    /   \
   B     E
  / \   / \
 C   D F   G

Which algorithm should I use?

BFS performs better when searching values that are closer to the source. DFS is a better option when searching values that may be further from the source and is typically the safer choice.

Because BFS searches each neighbor first, it is not an ideal solution for decision making trees. DFS is a better solution for decision making trees because once a value is targeted you will be interested in the paths that extend from that value.

BFS and DFS are the most elementary examples of search algorithms; they can become much more intricate and complex. Determining which algorithm is best depends on many factors, such as the ordering of the data (is it sorted? roughly sorted? in random order), and the structure of the data (is it hierarchical?). It is also important to recognize the constraints of the system running your search program: is it memory-sensitive, or CPU-sensitive? In short, there is no universal "best" search algorithm - but luckily, this isn't a new problem in the computer science community, so there are many resources to help make this decision.

Resources

1. Visualization of BFS and DFS on VisuAlgo.
2. Searching Algorithms on GeeksforGeeks.