Breadth First Technique

This means traversing the nodes layer-by-layer.Breadth First Traversal for a graph is similar to Breadth First Traversal of a tree .The only catch here is, unlike trees, graphs may contain cycles, so we may come to the same node again. To avoid processing a node more than once, we use a boolean visited array. For simplicity, it is assumed that all vertices are reachable from the starting vertex.Watch this for better understanding.

“Immediate neighbour nodes first then other nodes.“

/** This function ensures traversal in case of cycles in graph **/
void BFSfunc( vector<int> adj[] , int V)     
{
     bool visited[V+1];
     memset( visited , false , sizeof(visited) );
     for(int i = 0 ; i < V ; i++ )
     {
          if( visited[i] == false )
               BFS( adj , i , visited );
     }
}

void BFS( vector<int> adj[] , int s , bool visited[])
{
     queue<int> q;
     visited[s]=true;
     q.push(s);
     while( !q.empty() ){
          int u=q.front();
          q.pop();
          cout<<u<<" ";
          for( int x: adj[u] )
          {
               if( visited[x] == false )
               {
                    visited[x]=true;
                    q.push(x);
               }
     }}
}

Applications of BFS:-

• Find shortest path in an unweighted graph
• Social networking sites use this in search feature
• Cycle detection in graph
• Torrent or peer to peer network ,and many more.

This article has been contributed by Prashant Singh Thakur