Breadth First Search

Graph traversals

Graph traversal means visiting every vertex and edge exactly once in a well-defined order. While using certain graph algorithms, you must ensure that each vertex of the graph is visited exactly once. The order in which the vertices are visited is important and may depend upon the algorithm or question that you are solving. During a traversal, it is important that you track which vertices have been visited. The most common way of tracking vertices is to mark them.

Breadth First Search (BFS)

There are many ways to traverse graphs. BFS is the most commonly used approach. BFS is a traversing algorithm where you should start traversing from a selected node (source or starting node) and traverse the graph layerwise thus exploring the neighbor nodes (nodes which are directly connected to source node). You must then move towards the next-level neighbor nodes.

Pseudocode

BFS (G, s)  //Where G is the graph and s is the source  node
      let Q be queue.
      Q.enqueue( s ) 
      mark s as visited.
      while ( Q is not empty)
           v  =  Q.dequeue( )

          //processing all the neighbours of v  
          for all neighbours w of v in Graph G
               if w is not visited 
                        Q.enqueue( w ) 
                        mark w as visited.

0-1 BFS

This type of BFS is used to find the shortest distance between two nodes in a graph provided that the edges in the graph have the weights 0 or 1. If you apply the BFS explained earlier in this article, you will get an incorrect result for the optimal distance between 2 nodes.

In this approach, a boolean array is not used to mark the node because the condition of the optimal distance will be checked when you visit each node. A double-ended queue is used to store the node. In 0-1 BFS, if the weight of the edge = 0, then the node is pushed to the front of the dequeue. If the weight of the edge = 1, then the node is pushed to the back of the dequeue.

Implementation

Here, edges[ v ] [ i ] is an adjacency list that exists in the form of pairs i.e. edges[ v ][ i ].first will contain the node to which v is connected and edges[ v ][ i ].second will contain the distance between v and edges[ v ][ i ].first.

Q is a double-ended queue. The distance is an array where distance[ v ] will contain the distance from the start node to v node. Initially, the distance defined from the source node to each node is infinity.

This only applies to the small data set, if V is a huge number, can not use it, it will ou of memory.

void bfs (int start)
{
    deque <int > Q;     //Double-ended queue
    Q.push_back( start); 
    distance[ start ] = 0;       
    while( !Q.empty ())
    {
        int v = Q.front( );
        Q.pop_front(); 
        for( int i = 0 ; i < edges[v].size(); i++)
        {
            if(distance[ edges[ v ][ i ].first ] > distance[ v ] + 
                                           edges[ v ][ i ].second ) 
            {
                distance[ edges[ v ][ i ].first ] = distance[ v ] + 
                                             edges[ v ][ i ].second;
                if(edges[ v ][ i ].second == 0)
                {
                    Q.push_front( edges[ v ][ i ].first);
                }
                else
                {
                    Q.push_back( edges[ v ][ i ].first);
                }
            }
        }
    }
}