Breadth First Search (BFS)

📌Hello friends! In this post I am going to explain about Breadth First Search (BFS).What is the algorithm/ How we trace algorithm with the help of example. 

Breadth First Search is a Graph Traversal Methods.It is a technique used to search a vertex in a graph breadth wise. It is also used to decide the order of vertices to be visited in the search process.

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

ALGORITHM FOR BREADTH FIRST SEARCH:

STEP  1 : Set status of all vertex = 1 i.e ready to process state.

STEP 2 : INSERT the starting vertex on to the QUEUE and set its STATUS =2 i.e               waiting state.

STEP 3 : Repeat the following step until the QUEUE is not empty.

     STEP 3.1 : DELETE first vertex from QUEUE  and set its STATUS=3                                    i.e processed state.Call this vertex as NODE.

    STEP 3.2 : Now check all neighbours (adjacent vertex) of this NODE as                             follows.

          STEP 3.2.1 : If STATUS (Neighbour =1) than INSERT this neighbours into                              QUEUE and set its STATUS = 2 i.e waiting state.

           STEP 3.2.2 : ELSE If STATUS (Neighbour =2 or 3) than leave the                                          neighbour.

           

STEP 4 : END Loop

STEP 5 : End.

EXAMPLE:

let traverse the graph by using Breadth First Search

Now trace the above graph using algorithm:

STEP  1 : Set status of all vertex = 1 i.e ready to process state.

STEP 2 : INSERT the starting vertex on to the QUEUE and set its STATUS =2                 i.e waiting state.

STEP 3 : Repeat the following step until the QUEUE is not empty.

     STEP 3.1 : DELETE first vertex from QUEUE  and set its STATUS=3                                    i.e processed state.Call this vertex as NODE.

 STEP 3.2 : Now check all neighbours (adjacent vertex) of this NODE as                             follows.

here neighbour of A is [B,C]

STEP 3.2.1 : If STATUS (Neighbour =1) than INSERT this neighbours into                              QUEUE and set its STATUS = 2 i.e waiting state.

NOW AGAIN GO TO THE STEP 3

STEP 3 : Repeat the following step until the QUEUE is not empty.

     STEP 3.1 : DELETE first vertex from QUEUE  and set its STATUS=3                                    i.e processed state.Call this vertex as NODE.

 STEP 3.2 : Now check all neighbours (adjacent vertex) of this NODE as                             follows.

here neighbour of B is [A,D,E] , But A is already processed So processed with D & E.

STEP 3.2.1 : If STATUS (Neighbour =1) than INSERT this neighbours into                              QUEUE and set its STATUS = 2 i.e waiting state.

NOW AGAIN GO TO THE STEP 3

STEP 3 : Repeat the following step until the QUEUE is not empty.

     STEP 3.1 : DELETE first vertex from QUEUE  and set its STATUS=3                                    i.e processed state.Call this vertex as NODE.

STEP 3.2 : Now check all neighbours (adjacent vertex) of this NODE as                             follows.

here neighbour of C is [A,D,E] , But A is already processed So processed with D & E.

STEP 3.2.1 : If STATUS (Neighbour =1) than INSERT this neighbours into                              QUEUE and set its STATUS = 2 i.e waiting state.

STEP 3.2.1  is false so we Go in STEP 3.2.2 i.e

 STEP 3.2.2 : ELSE If STATUS (Neighbour =2 or 3) than leave the                                          neighbour.

so from STEP 3.2.2 just ignore D & E. and GO TO STEP 3 i.e

STEP 3 : Repeat the following step until the QUEUE is not empty.

     STEP 3.1 : DELETE first vertex from QUEUE  and set its STATUS=3                                    i.e processed state.Call this vertex as NODE.

STEP 3.2 : Now check all neighbours (adjacent vertex) of this NODE as                             follows.

here neighbour of D is [B,C] , But B & C is already processed.

STEP 3.2.1 : If STATUS (Neighbour =1) than INSERT this neighbours into                              QUEUE and set its STATUS = 2 i.e waiting state.

STEP 3.2.1  is false so we Go in STEP 3.2.2 i.e

 STEP 3.2.2 : ELSE If STATUS (Neighbour =2 or 3) than leave the                                          neighbour.

so from STEP 3.2.2 just ignore B & C. and GO TO STEP 3 i.e

STEP 3 : Repeat the following step until the QUEUE is not empty.

     STEP 3.1 : DELETE first vertex from QUEUE  and set its STATUS=3                                    i.e processed state.Call this vertex as NODE.

So finally we get:

Now here the queue become empty so it a end of algorithm.

We get following path i.e [A➞ B➞ C➞ D➞ E]. on the basis of path tree will be: 

This tree is also known as Breadth first Spanning tree.

📌Friends ! This is all about Breadth First Search (BFS).So I hope you understand the working of  BFS  algorithm. Example is also clear the concept.This is end of this post so we will meet in next post till continue reading.