BFS (Breadth First Search)

BFS is an algorithm to traverse the graph or tree.

Prerequisite:
1. For Simplest example take 2D array.
2. Take a visited 2D array.

Procedure :
1. First select any root Node or you can simply start the first row and first col of the matrix as below

traverseMatrix(0 , 0);

2. Mark the root Node as visited and add the Node in Queue.(Before this step , create a structure of type Node)

Node Structure:

static class Node{
int _row ;
int _col;
Node(int row , int col){
this._row = row;
this._col = col;
}
}

Now add to Queue as explained in Step 2 as follows and here we are assigning 0 to processed Node.

  mVisited[row][col] = true;
mMatrix[row][col] = 0;
Queue mQueue = new LinkedList<>();

Node mNode = new Node(row , col);
mQueue.add(mNode);

3. Now process the queue until it becomes empty.
    while(!mQueue.isEmpty())

4. Poll an element from the queue and find its neighbors
    Node mExNode = mQueue.poll();

The neighbors can be find either in 4 directions or in 8 directions.

 4 Directions:
 LEFT , RIGHT , TOP , DOWN

 8 Directions:
LEFT , RIGHT , TOP , BOTTOM , TOP-LEFT, TOP-RIGHT, BOTTOM-LEFT, BOTTOM-RIGHT

Node mExNode = mQueue.poll();

int mRow  = mExNode._row;
int mCol =  mExNode._col;
for (int i = 0; i < dx.length; i++) {
int x = mRow +  dx[i];
int  y =  mCol +  dy[i];

...................................
}

Where dx and dy as follows

// below dx and dy are two direction matrix
static int dx[] = {-1, 1, 0, 0, -1, -1, 1, 1};
static int dy [] = {0, 0, -1, 1 , 1, -1, -1, 1};

5. Add the neighbors in a queue if not visited before.
6. Mark the Node visited and

                                 if(isSafe(x , y)){
mMatrix[x][y] = 0;
mVisited[x][y] = true;
mQueue.add(new Node(x , y));
  }

Where isSafe(x , y)  is as below

private static boolean isSafe(int row, int col) {
if(row >= 0 && row < R && col >= 0 && col < C && !mVisited[row][col])
return true;
return false;

}

7. Repeat the step 4 until the queue becomes empty.


Question : Traverse the whole matrix using BFS.
Solution  : Please check the below Code Snippet

Complete Code Snippet :


Output :

0 0 0 0 0 0 
0 0 0 0 0 0 
0 0 0 0 0 0 
0 0 0 0 0 0 
0 0 0 0 0 0 
0 0 0 0 0 0