Programming Game AI by Example

Implementing the Algorithm

The algorithm for BFS is almost exactly the same as for DFS except it uses

a first in, first out (FIFO) queue instead of a stack. Consequently, this time

edges are retrieved from the queue in the same order they are put onto the

queue. Take a look at the source code for the BFS

Search method.

template <class graph_type>

bool Graph_SearchBFS< graph_type>::Search()

{

//create a std queue of pointer's edges

std::queue<const Edge*> Q;

//create a dummy edge and put on the queue

const Edge Dummy(m_iSource, m_iSource, 0);

Q.push(&Dummy);

//mark the source node as visited

m_Visited[m_iSource] = visited;

//while there are edges in the queue ...