Breadth first

The breadth first search is the simplest of search algorithms. It explores all directions equally. So how does it explore? Well, in all of these search algorithms, the key idea is to keep track of an expanding area, referred to as the frontier. The breadth first algorithm expands this frontier by moving out from the starting point and checking its neighbors first, then its neighbor's neighbors, and so on. The following is a diagram showing how this expansion takes place on a grid. The numbers denote the order the grid square was visited:

A simple example of how we can implement this in C++ follows. I have left out a few sections of code for the sake of space in the book. The full implementation can be found in the Chapter09 example project, in the source code repository:

void SearchGraph::BreadthFirst(int s) 
{ 
    // Mark all the vertices as not visited 
    bool *visited = new bool[V]; 
    for(int i = 0; i < V; i++) 
        visited[i] = false; 
  
    // Create a queue for BFS 
    list<int> queue; 
  
    // Mark the current node as visited and enqueue it 
    visited[s] = true; 
    queue.push_back(s); 
  
    // 'i' will be used to get all adjacent vertices of a vertex 
    list<int>::iterator i; 
  
    while(!queue.empty()) 
    { 
        // Dequeue a vertex from queue and print it 
        s = queue.front(); 
        cout << s << " "; 
        queue.pop_front(); 
  
        // Get all adjacent vertices of the dequeued vertex s 
        // If a adjacent has not been visited, then mark it visited 
        // and enqueue it 
        for(i = adj[s].begin(); i != adj[s].end(); ++i) 
        { 
            if(!visited[*i]) 
            { 
                visited[*i] = true; 
                queue.push_back(*i); 
            } 
        } 
    } 
} 

As you may have noticed from the source code, one trick with this algorithm is we need to avoid doubling back and processing a node more than once. In this simple example, we implement an array of Boolean values of visited nodes. If we don't mark visited vertices in this example, we create an endless loop process.

This is an incredibly useful algorithm, not only for regular pathfinding but also for procedural map generation, flow field pathfinding, distance maps, and other types of map analysis.