Breadth First Search on a Grid

John DeRiggi
Nov 4 · 3 min read

I used to think BFS was scary. It’s not that bad. Want a good data structure to practice on but can’t be bothered to generate a complex graph? Just make a grid with some obstacles! You can also use your file system for a tree, maybe that will be in the write up for the next post. For this case we’ll use a grid. A good old 2-D array. Let’s fill up a board with some non-negative integers:

void iterativeFill(int[][] b){
int x = 0;
for(int i = 0; i < b.length; i++){
for(int j = 0; j < b[i].length; j++){
b[i][j] = x++;
}
}
}

Let’s put some obstacles in random positions within each row . We will put numPerRow obstacles as -1 values in the grid as long as the obstacle is not our target element.

void randomObstacles( int[][] board, int numPerRow, int target){
for (int r = 0; r < board.length; r++ ){
for(int s = 0; s < numPerRow; s++){
int randomColumn = (int)(Math.random()*board[r].length);
if(board[r][randomColumn] != target){
board[r][randomColumn] = -1;
}
}
}
}

Now the overall loop for BFS is to:

  • remove an item from the queue
  • check if we found our target
  • mark it as visited
  • add this cell’s neighbors to the queue but only if those neighbor are un-visited, non-obstacles, and within bounds of the grid

Also, we will track the cells we visit so we can print our grid as we search and watch bfs go to work. For this case, we will make the searcher a little handicapped, limiting it’s movement to up or right only. This will give us some interesting cases depending on the obstacle layout that will prevent it from finding the target.

Here’s our grid with obstacles in the -1 cells. Let’s set our target as the cell with value 28 and our origin to the lower left cell.

Get ready for some stunning visuals:

our grid with -1 as obstacles and cell 28 as the target

Let’s highlight the start, finish, and obstacles along the way

Now let’s watch BFS do it’s thing.

Here’s the complete code.

So what is the complexity on this bad boy? Well worst case is approximately close to every cell and every cell’s two edges, since we only look up and right.

Let’s let’s visualize part of the runtime by looking at the number of BFS loops we hit on a 10 by 10 matrix. At 1000 runs we get a median of 58, 90th percentile of 66 and a 10th percentile at 35

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade