Breadth-first search(BFS)

BFS  is aslo a method for processing the vertices or  edges  of a graph in  a systematic order.The  procedure  is as follows

1. Visit  a vertex of a graph arbitrarily and mark it as being visited
2. All  the vertices which are adjacent to previously visited vertex are visited sequentially
3. Repeat the above step for next level and continue till  all the vertices are visited in that connected component
4. if some vertices are still  remaining repeat the step1

• We will use the queue data structure to trace the operation of BFS
• The first vertex of the traversal becomes the initial value of the queue
• ie, the element at the front vertex on  each iteration,the algorithm finds the vertices which are adjacent to the front vertex
• These vertices are inserted into the queue and the front vertex is deleted from the queue
• As  in DFS  ,for  BFS  also we will construct a BFS  forest
• The starting vertex of the traversal  will  be the root of one tree in BFS 
• Whenever  a new  node is visited that must be attached to a previous node as a child,such an edge is known as tree-edge
• Whenever a node finds an edge to already visited vertex other  than its parent then it is treated as cross-edge