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.