Breadth First Search(1)

Breadth First Search

 

The idea is to visit of the vertices at distance 'k' from the current vertex before visiting the vertices at distance 'k+1' 

Explanation

 

Applying BFS is a very simple algorithm, Just follow the below steps of the flowchart.

Before starting the algorithm, Remember these terms:

 

1) Life is white sheet of paper : so a white vertex in graph means the vertex has not been visited yet

2) Once you start writing your life with a pencil, it will turn gray : so a gray vertex in graph means the vertex is being visited

3) Finally, you die and your ashes turn black : so a black vertex in graph means the vertex has been visited

 

Flowchart

 

Let us have the below graph in the left, and an empty queue Q in the right

Now, use the flowchart and keep matching your steps with my steps:

 

Choose any vertex as your starting point of algorithm, let us choose vertex s. Color all vertices as white except vertex s, color vertex s as gray.

 

Fig 1:

Enqueue vertex s.

Fig 2: 

Q is empty?

No.

dequeue(Q)

prints s

 

choose a neighbour of s

let us choose w

w is white?

Yes.

color w as gray

Fig 3: 

Enqueue(w)

Fig 4: 

 

choose a neighbour of s

let us choose r

r is white?

Yes.

color r as gray

Fig 5:

Enqueue(r)

Fig 6:

 

choose a neighbour of s

But.....see, now we don't have any white neighbour of s

so s is completed now.

color s as black

Fig 7:

Q is empty?

No.

dequeue(Q)

prints w

Fig 8: 

choose a neighbour of w

let us choose t

t is white?

Yes.

color t as gray

Fig 9:

Enqueue(t)

Fig 10: 

choose a neighbour of w

let us choose x

x is white?

Yes.

color x as gray

Fig 11: 

Enqueue(x)

Fig 12: 

 

choose a neighbour of w

But.....see, now we don't have any white neighbour of w

so w is completed now.

color w as black

Fig 13: 

Q is empty?

No.

dequeue(Q)

prints r

Fig 14: 

choose a neighbour of r

let us choose v

v is white?

Yes.

color v as gray

Fig 15: 

Enqueue(v)

Fig 16: 

choose a neighbour of r

But.....see, now we don't have any white neighbour of r

so r is completed now.

color r as black

Fig 17: 

Q is empty?

No.

dequeue(Q)

prints t

Fig 18: 

choose a neighbour of t

let us choose u

u is white?

Yes.

color u as gray

Fig 19: 

choose a neighbour of t

But.....see, now we don't have any white neighbour of t

so t is completed now.

color t as black

Fig 20: 

Q is empty?

No.

dequeue(Q)

prints x

Fig 21: 

choose a neighbour of x

let us choose y

y is white?

Yes.

color y as gray

Fig 21: 

Psuedocode

 

BFS(G,s)

{

 

for each vertex v in G except s:

{

      v.color=white;

}

 

s.color=gray;

 

enqueue(Q,s);

 

while(Q is not empty)

{

      u=Dequeue(Q);

      print(u);

            

            for(all neighbours v of u)

            {

                        if(v.color==white)

                        {

                                    v.color=gray;

                                    Enqueue(Q,v);

                         }

                       

                        u.color=black;

            }

}

 

}

 

Time complexity

 

BFS has a time complexity of O(V+E) if we have graph stored in an adjacency list, and O(V2) if we have graph stored in an adjacency matrix.

0Comment