# BFS traversal

BFS is similar to the level order traversal.BFS uses queues as a data structure and an array to implement BFS traversal of a graph

BFS Algorithm

- Get an array of size of the number of vertices
- Initialize Queue is empty
- Enqueue the first node and mark it as visited
- while the Queue is not empty
- Dequeue the value from the queue
- Enqueue all adjacent vertices into the queue
- marks this enqueue vertices as visited
- If no vertex is left to be enqueued then repeat step 4.1

here initialize empty queue, and created an output array for BFS output and a non visited array with values 0, to indicate that the node is visited or not.select node 3 as the starting node.

Step1: insert 3 into the queue, now check 3 in the visited array,move 3 to the output array, insert adjacent nodes of 3, that is 1,5 into the queue

mark 1 and 5 node as visited in the visited array.

Step 2:front pointer is at 1, insert 1 into the queue, now check 1 in the visited array, move 1 to the output array, insert adjacent nodes of 1 ,that is 2,4 into the queue

check 2 and 4 node as visited in the visited array.

step 3: front pointer is at 5, insert 5 into the queue, now check 5 in the visited array, move 5 to the output array, don’t insert adjacent nodes of 5, that is 4 into the queue, because they are already visited

step 4: front pointer is at 2, insert 2 into the queue, now check 2 in the visited array, move 2 to the output array, don’t insert adjacent nodes of 2, that is 4 into the queue, because they are already visited

step 5: front pointer is at 4, insert 4 into the queue, now check 4 in the visited array, move 4 to the output array, don’t insert adjacent nodes of 4, that is 3 into the queue, because they are already visited