Breadth First Search (BFS) algorithm is used to traverse a graph in a breadthward motion. BFS Algorithm use data structure queue to remember to get the next vertex to start the search and we will requred an array to keep the track of vertex that it is visited or unvisited.

In BFS traversal we start the source vertex, display and mark it as visited and look for its adjacent vertices which are unvisited, display them and mark them visited and put them in the queue. If we  not found any adjacent vertex to the source node which is unvisited then, we pop out the first element of queue and do the same thing for the popped element. This steps will be repeated until the queue becomes empty.

Algorithm:

 

1. Mark all the vertices unvisited
2. set: source=vertex from where we want to start BFS traversal
3. let vertex_status[]
       #This array is used to track that the vertex is vistied or not
4. let graph_matrix[][] is the adj_matrix of graph having n nodes
        
       #if ith and jth node is connected then graph_matrix[i][j]=1
         else graph_matrix[i][j]=0

5. Display the source vertex and mark it as visited.
6. push the sourve vertex to the Queue
7. do While Queue is not empty:
8.     set: source=queue.front
9.         Update Queue by deleting pop out front element
10.    do For i=1 to n:
11.        If graph_matrix[source][i]=1 and vertex_status[i]=unvisited:
12.                    Display vertex 'i' and mark it as visited
13.    EndFor
14. EndWhile

Example:
 

 
Traversal: 

Let's start the traversal in the above exam from vertex 1

Let:         source=1
Display:  source=1
Set:         vertex_status[source]=vertex_status[1]=visited
Do:         que.push(source) /* pushing the source vertex in queue */

                 Output                                 Updated  Queue                                       Visited Vertex

                 1                                            1                                                                  1

Now do While Queue is not empty

Pass   1:        

Pop out first element of queue that is 1, and now adjacent unvisited vertices of the vertex 1 are 2 and 5. Now we display them and put in the Queue. Updated table is given below.             

                Output                                 Updated  Queue                                        Visited Vertex

                1 2 5                                      2 5                                                               1 2 5

Pass   2:  

Pop out the first element of queue and which is 2 and look for the adjacent unvisited vertices of vertex 2 and which is only 3 because 5 and 1 is already visited. Now display 3 and put it into the queue. Updated table is given below.

                Output                                 Updated  Queue                                        Visited Vertex

                1 2 5 3                                  5  3                                                               1 2 5 3

Pass   3:  

Pop out the first element of queue and which is 5 and look for the adjacent unvisited vertices of vertex 5 which is only 4 because 2 and 1 is already visited. Now display 4 and put it into the queue. Updated table is given below.

               Output                                 Updated  Queue                                        Visited Vertex

               1 2 5 3  4                              3 4                                                               1 2 5 3 4

Pass   4:  

Pop out the first element of queue and which is 3 and look for the adjacent unvisited vertices of vertex 3 but there is no any unvisited adjacent vertex due to which no element is displayed. Updated table is given below.

               Output                                 Updated  Queue                                        Visited Vertex

               1 2 5 3 4                               4                                                                   1 2 5 3 4

Pass   5:  

Pop out the first element of queue and which is 4 and look for the adjacent unvisited vertices of vertex 4
which is only 6 because 3 is already visited. So display 2, mark it as visited and put it into the queue. Updated table is given below.

               Output                                 Updated  Queue                                        Visited Vertex

               1 2 5 3 4 6                            6                                                                  1 2 5 3 4 6

Pass   6:  

Pop out the first element of queue and which is 6 and look for the adjacent unvisited vertices of vertex 6.
Therefore no element will be displayed.

               Output                                 Updated  Queue                                        Visited Vertex

               1 2 5 3 4 6                                                                                                 1 2 5 3 4 6

Now queue becomes empty therefore while loop will terminate.

Implementation of the above Algorithm in C++

 


#include <stdio.h>
#include <queue>
#define MAX 100
#define visited 2
#define unvisited 1
using namespace std;

class bfs_traversal
{
   private:
        std::queue <int> que;
        int vertex_status[MAX],graph_matrix[MAX][MAX];
        int n;
      public:
           void get_data();
           void bfs_traverse();
};
void bfs_traversal::get_data()
{
   printf("\nEnter the total number of vertices: ");
   scanf("%d",&n);
   int max_edge=n*(n-1)/2;
   int i,source,destination;
   for(i=1;i<=max_edge;i++)
   {
            printf("\nEnter the source and destination of vertex %d and (0,0) to Exit:\n",i);
            scanf("%d%d",&source,&destination);
            if(source==0 && destination==0)
            {
                  break;
            }
            else
            {
                  graph_matrix[source][destination]=1;
                  graph_matrix[destination][source]=1;
            }
   }
}
void bfs_traversal::bfs_traverse()
{
      int i;
      for(i=1;i<=n;i++)
      {
            vertex_status[i]=unvisited;
      }
   int source;
   printf("\nEnter the source from where you want to start traversing: \n");
   scanf("%d",&source);
   printf("\n%d ",source);
   vertex_status[source]=visited;
   que.push(source);
   while(!que.empty())
   {
         source=que.front();
         que.pop();
         for(i=1;i<=n;i++)
         {
             if(graph_matrix[source][i]==1 && vertex_status[i]==unvisited)
             {
                  printf("%d ",i);
                  vertex_status[i]=visited;
                  que.push(i);
             }
         }
   }
}
int main()
{
   bfs_traversal graph;
   graph.get_data();
   graph.bfs_traverse();
   return 0;
}

OUTPUT:
 

See also: C++ Program to traverse a graph using DFS