Column: Finding a shortest path and Breadth-first search

What is a Breadth-first search?

If you have a tree structure as below and visit the root node, and then all of its children, and all of its children’s children, and so on, that’s a so-called Breadth-first search. In this case, the order will be: A => B => C => D => E => F => G => H => I.

(John Song)

This is different from the depth-first search, where you traverse the tree in the “depth-first” way, meaning you go deep down until a leaf, back up and then another leaf, and then move on to the next node and all the way down to one of its leaves, and so on. The order in this case will be: A => B => E => F => C => G => D => H => I – more precisely, this is the pre-order traversal.

(John Song)

Then when would you use BFS?

Finding the shortest path is a good example. There’s a 10 x 8 grid and you want to find the shortest path from (0, 0) to (9, 7). Note there are some obstacles on it, which you should get around.

(John Song)

You’d first want to try the starting point’s neighbors, which are (1, 0) and (0, 1), and then their neighbors again, and so on, until you finally reach the goal. You also want to avoid any obstacles and any “cells” that you already visited. In order to avoid visiting a cell that you already did, you can use a hash set structure (e.g. std::unordered_set in C++), where you store visited cells, and check the cell you’re about to visit against the set before you decide to visit it.

(John Song)

(John Song)

Here’s a quick/simple algorithm for BFS.

(John Song)

Would you like to implement your own?