BFS in Practice

                                   BFS in Practice 

      BFS, in general, stands for Breadth Frist Search in a graph. It has the same time complexity with DFS in a graph but tends to have more space complexity especially when the branching factor of a graph is big. However, as a trade-off, BFS is guaranteed to give the optimal solution, which means if we could find the target, then the path we used to find the target is guaranteed to be the shortest path or the path with the same distance value. 

     We have talked about this topic a long time ago in my previous blog posts. But here are two reasons for this new post 1. Explore the elegant way to write BFS code in a fairly complicated problem 2. BFS also could stands for Best First Search in a graph and we will look at examples for this algorithm. 

1. Level order print Binary Tree 

For example:
Given a binary tree

    3
   / \
  9  20
    /  \
   15   7

return its level order traversal as:

[
  [3],
  [9,20],
  [15,7]
]

--------------------------------------------------------------------------

This is a classic problem for breadth-first search, where we use a queue to swipe the binary tree level by level. Here is the  solution in Java:

2. Walls and gates 

Given a  m x n 2D grid initialized with these three possible values.

1. -1 - A wall or an obstacle.
2. 0 - A gate.
3. INF - Infinity means an empty room. We use the value to231 - 1 = 2147483647 represent asINF you may assume that the distance to a gate is less than.2147483647

Fill each empty room with the distance to its nearest gate. If it is impossible to reach a gate, it should be filled with.INF

Example: 

Given the 2D grid:

INF  -1  0  INF
INF INF INF  -1
INF  -1 INF  -1
  0  -1 INF INF

After running your function, the 2D grid should be:

  3  -1   0   1
  2   2   1  -1
  1  -1   2  -1
  0  -1   3   4

---------------------------------------------------------------------------

What is your first algorithm after reading the problem? Well, my first algorithm is to do BFS start from each empty room position. The algorithm will find give the optimal solution by the property of BFS.  However, because of 1.  The number of gates is less than the number of empty rooms (At least in this example, and possibly in general).  2. The number 0 represents the gate, which could also represent its distance to the nearest gate ( the distance to its self is 0). We could consider doing BFS start from every gate and the then reach every possible empty room.

Here is the solution based on the above-revised algorithm:



Note: 1. We could use new int[]{i, j} to store a coordinate, which save us time to create a node class

          2. How to search each 4 direction efficiently? Line 13 is a handy way to do this (Actually is line 13 and 16-19 could generate coordinates for up, down, right and left directions)

3. Number of Islands 

Given a 2d grid map of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Example 1:

Input:
11110
11010
11000
00000

Output: 1

Example 2:

Input:
11000
11000
00100
00011

Output: 3

--------------------------------------------------------------------------

This is also a very classic problem. I think it appears on my entry-level data structure textbook. To solve this problem we will traverse the input grid, increment the counter by 1 every time we see a "1" in location grid[i][j].  Then start from grid[i][j] we do a BFS to mark all the connected value
"1" as 0, which will make sure we only increment out counter by 1 for each island.

Here is the solution code:



Note: To do a search on every 4 directions we used the trick in line 16 and 22-25 again. Besides, new int [] { i, j} could be used to store a coordinate. 

4. Best First Search 

From the name of this algorithm, we could indicate that the "best" node, which certainly will be different according to each problem's definition, has the highest priority to be searched(expanded). Therefore, a priority queue is often used in this algorithm to find the next "best" node to expand.

 Each Best First algorithm will have 3 components:

1. Initial state (Start node) 
2. Node expansion rule 
3. Termination condition 

Example 1: 

The classic Dijkstra's Algorithm for Single Source Shortest Path(SSSP) is also a deviation of Best First Search. Here are the 3 components for Dijkstra's algorithm:

1. Initial state -> the source node has distance = 0, other nodes have distance = +INFI
2. Node expansion rule -> cost = (a). Cost of parent node + distance from the parent node to the current node
(b). The current node that has the lowest value will be pop up first ( have the highest priority)
(c). Each time the best node being popped up, we update all it's neighbor's distance using the rule (a) above.
3. Termination condition -> When priority queue becomes empty (Completed all reachable nodes in the graph)

Example 2:

Given a matrix of size N*N, and for each row, the elements are sorted in ascending order, and for each column, the elements are also sorted in ascending order. How to find the K-th smallest element in it?


Solution:

1. Initial state (start node) input[0][0]
2. Node expansion/generation rule: expand node[i][j]
         a. -> generate[i+1][j]
         b. -> generate[i][j+1]
3. Termination condition:
         a. When the k-th element is popped out for expansion, then we use it to return

4.* Be careful about (De-duplication for generated states)


5. Destroy Monsters Game 
(Multiple Breadth First Search) 


Given a 2D array, where for each cell, value 0 means walls (cannot across), value 1 means path, and value 2 and above means monsters. We want to find the shortest path starting from the point(0, 0), find and destroy all the monster with value 2 (after a monster being found and destroyed, the cell value will change to 1), then find an destroy all the monster with value 3, then monster with value 4... Until we destroyed all the monsters in the graph.

*for the purpose of easy demonstration, let's just assume the maximum monster has value 3.



If we want to reach all the 4 levels we easily add as:






Hope you enjoy the game :-)

Kind Regards ^^
Ye Jiang