Breadth First Search (BFS)

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.

BFS full video tutorial with code

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

Write a comment