Breath First Search (BFS) is another graph traversal algorithm. In BFS, we expand the neighbour nodes or links for any node first, before moving to next level neighbours. We can implement this using a simple queue i.e. "first in, first out" (FIFO). It is guaranteed to find the shortest path to goal state.

It is memory intensive (uses more memory than DFS) if the state space is large.

Algorithm Edit

BFS starts with insertion of initial source vertex s into a queue, then processes the queue as follows: take out the front most vertex u from the queue and enqueue each of the unvisited neighbours of u. With the help of the queue, BFS will visit vertex s and all vertices in connected component that contains s layer by layer. This is why it is named breath-first. BFS algorithm also runs in O(V+E) on a graph represented using an Adjacency list.

vector < pair<int, int> > AdjList;   
void BFS(int n)
   queue<int> q;
   map<int, int> dist;

       int u = q.front();
       printf("Visit %d, Layer %d\n", u, dist[u]);
       for(auto const& v: AdjList[u])
               dist[v->first] = dist[u]+1;

Here, we use queue to order the sequence of visitation and map to record if a vertex has been visited or not - which at the same time records the distance (layer number) of each vertex from source vertex. This is important as it can be used to solve the special case of Single-Source Shortest Paths problem as discussed below.

Other Applications Edit

Single-Source Shortest Paths (SSSP) on Unweighted Graph Edit

The fact that BFS visits vertices of a graph layer by layer from a source vertex turns BFS as a good solver for Single-Source Shortest Paths (SSSP) problem on unweighted graph. This is because in unweighted graph, the distance between two neighbouring vertices connected with an edge is simply one unit. Thus the layer count of a vertex that we have seen previously is precisely the shortest path length from source to that vertex.

See Also Edit