Implementation of BFS

In this lesson, we will implement Breadth-first Search to solve the shortest path problem for unweighted graphs.

Implementation Notes

When implementing DFS previously, we wanted to explore the deepest unexplored node first. This corresponds to using a stack for the unexplored nodes, which is a Last-In-First-Out (LIFO) data structure. Uusually the stack is implicit in the recursive implementation.

For implementing BFS, we want to do the opposite and explore the closest unexplored node first. Hence, we’ll use a queue to store the unexplored nodes, which is a First-In-First-Out (FIFO) data structure.