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:

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"
                    EnQueue( n )
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