Breadth First Search & Depth First Search

Implementation and Comparison

In the post here we implemented breadth first search and used it to find an optimal path in a 2D grid world. The implementation took 2 steps:

1. Going forward from the init state and record the expanding process
2. Going backward from the goal state to find the optimal path

One caveat is that the algorithm was not able to find multiple optimal path and the implementation is a bit lengthy. In this post, we will introduce more elegant and concise implementations of both breadth first search and depth first search.

Problem Settings

Suppose we have a graph setting as below:

our goal is to find all paths from A to F.

We then put the graph into a python dictionary:

BFS

The key of this breadth first search is still to:

1. Maintain a queue that is able to pop out the current lowest level node