Breadth First Search (BFS) Traversal

Introduction

Implementation of BFS is very important in path finding algorithms. This is simply analogous to the motion of water waves once a stone is dropped at a point.

 

As we can see in the above picture in BFS for each node the neighbours are discovered first. They the neighbours of neighbours are discovered. Thus the propgation is analogous to the ripple effect.

Let's see how that happens from the above simple tree starting from 1 as the vertex point.

we have 1 so discover its neighbours as 2, 3, 4

In the mean time we maintain a queue to keep the item to be visited next

Q = {2,3,4}

Now we take 2 out and discover its neighbours while updating Q

Q = {3,4,5,6}

Like wise we are continuing the procedure until the queue we started with gets empty. In a tree we are not required to remember visited nodes since there are no connection between nodes in the same level (5 and 6 are not connected, i.e no closed loops). But this is not the case for a graph. Thus we need to keep track of the visited nodes. For this we are using a HashMap in java. This is because we can quickly check if a node is visited ( in O(1) time).

Programming

The algorithm can be elaborated in Pseudo code as follows

function BFS(vertex):

    Q = queue()

    visited = hashmap()

    Q.add(vertex)

    while(Q.size > 0):

        n = Q.dequeue()

        for neighbours v of n:

            if( v not in visited):

                Q.add(v)

            else:

            continue
    visited.add(n)

Programmed Java code is as follows