## Breadth-first search (BFS)

Breadth-first search (BFS) is an algorithm that traverses a graph in
search of one or more goal nodes. As we will discover in a few weeks, a
maze is a special instance of the mathematical object known as a "graph".
In the meantime, however, we will use "maze" and "graph"
interchangeably.

The defining characteristic of this search is that, whenever BFS
examines a maze cell *c*, it adds the neighbours of *c* to a set
of cells which it will to examine later. In contrast to DFS, these cells
are removed from this set in the order in which they were visited; that
is, BFS maintains a *queue* of cells which have been visited but not
yet examined (an examination of a cell *c* consists of visiting all
of its neighbors).
Thus, a cell can have three states:

*Unvisited*. The cell has not yet been visited by BFS.
*Visited but Not Examined*. The cell has been discovered, but
BFS has not evaluated whether its neighbors should be added to the
Queue.
*Examined*. The cell has been visited, and all its neighbours
are/have been in the queue (ie, they are already "Visited but Not
Examined" or "Examined").

The algorithm for BFS is thus:

**Breadth-First-Search**( Maze *m* )
EnQueue( *m*.StartNode )
While Queue.NotEmpty
*c* <- DeQueue
If *c* is the goal
Exit
Else
Foreach neighbor *n* of *c*
If *n* "Unvisited"
**Mark ***n* "Visited"
EnQueue( *n* )
**Mark ***c* "Examined"
**End procedure**

The end result is that BFS will visit all the cells in order of their
distance from the entrance. First, it visits all locations one step away,
then it visits all locations that are two steps away, and so on, until an
exit is found. Because of this, BFS has the nice property that it will
naturally discover the shortest route through the maze.

See
this page for more information on BFS, and
this page for a graphical comparison of BFS and
DFS.

CSE 326 Summer 2002 Homepage