Graph Traversal - BFS

BFS (Breadth First Search)
BFS traversal of a graph produces a spanning tree as final result. Spanning Tree is a graph without loops. We use Queue data structure with maximum size of total number of vertices in the graph to implement BFS traversal.

Note:BFS Follows level order traversals of a given tree in its conclusion  


We use the following steps to implement BFS traversal...

Step 1 - Define a Queue of size total number of vertices in the graph.
Step 2 - Select any vertex as starting point for traversal. Visit that vertex and insert it into the Queue.
Step 3 - Visit all the non-visited adjacent vertices of the vertex which is at front of the Queue and insert them into the Queue.
Step 4 - When there is no new vertex to be visited from the vertex which is at front of the Queue then delete that vertex.
Step 5 - Repeat steps 3 and 4 until queue becomes empty.
Step 6 - When queue becomes empty, then produce final spanning tree by removing unused edges from the graph

Algorithm of BFS :

1. set status of all vertex=1
2. insert the starting vertex in queue and set its status=2
3. while(queue is not empty)
4.     remove front vertex in queue and set its status=3
5.     if(status of neighbors = 1)
6.     then insert neighbors in queue and set its status=2
7. end of while
8. exit

Example