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

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

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.

BFS traversal insert 3

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

BFS traversal insert 3

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

BFS traversal insert 1

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

BFS traversal insert 1

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

BFS traversal insert 5

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

BFS traversal insert 2

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

BFS traversal insert 4

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

Default image
Vishal Devxo
Vishal Devxo is a DevOps engineer and a Backend developer, he spends all his time for creating good tutorials with better visuals and blogging, developed some projects based on Python-Django, some hacking modules and scripts in python