Breadth first traversal for a Graph

Breadth First Traversal (BFS) is a graph traversal algorithm that visits all the vertices of a graph in breadth-first order, i.e., it visits all the vertices at the same level before moving to the vertices at the next level.

The algorithm starts at the root node (or any arbitrary node) of the graph and visits all its adjacent nodes (also called neighbors). Then, it visits all the unvisited nodes at the next level, and so on until all the vertices have been visited.

To keep track of the visited nodes, BFS uses a queue data structure. The algorithm works as follows:

1. Start by visiting the root node and enqueue it into a queue.
2. While the queue is not empty, dequeue the next node from the queue.
3. For each unvisited neighbor of the dequeued node, mark it as visited and enqueue it into the queue.
4. Repeat steps 2 and 3 until the queue is empty.

The order in which the nodes are visited by BFS forms a breadth-first search tree or level-order tree. BFS can be used to find the shortest path between two nodes in an unweighted graph, as the algorithm always visits the vertices in increasing order of their distance from the root node.