BFS Summary - Leetcode

0.Basic Concepts

Breadth First Search (BFS) is a method for traversing or searching tree or graph data structures.

1.When do we apply BFS?

It is frequently used to
  1) explore some features/characteristics in the tree/graph.
     [typical examples]
        [101] Symmetric Tree
        [261] Graph Valid Tree

  2) search for nodes/level/connected components
     [typical examples] search for nodes/connected components
        [133] Clone Graph
        [200] Number of Islands
        [323] Number of Connected Components in an Undirected Graph
        [286] Walls and Gates

     [typical examples] level related problem
        [102] Binary Tree Level Order Traversal
        [103] Binary Tree Zigzag Level Order Traversal
        [107] Binary Tree Level Order Traversal II
        [199] Binary Tree Right Side View

  3) shortest steps(path) 

     Utilizing BFS to find the shortest path involves a lot of details, so let's use an example to discuss it.

Example:

The solution needs to:

1)Utilize a matrix (int[][] distance) to record the shortest distance from node A to node (i, j). If we cannot reach the node (i, j), marked it as -1. 

2)Apply BFS to calc distance[][]. All distance[i][j] except the the start point should be initialized as -1; the start point distance is initialized as 0.

3)When updating the distance matrix using BFS, for each dequeued node, we will enqueue its unvisited grass neighbor (which means distance of an obstacle will always be -1. This also makes sense because -1 means unreachable):

Here we show the pseudo codes for this BFS process (which is also classical BFS codes):

Follow-up 1:

What if we can move in 8 directions? (up, upright, right, ...)

If you run the above code, you will meet a bug like this:

Why?

In the round 0, you dequeue A, and enqueue all nodes around A, which are (0,0), (0,1), (1,1), (2,1), (2,0)

In the round 1, you first dequeue (0,0), as we can see, for (0,0), its unvisited neighbors are (0,1), (1,1), so you will enqueue these two nodes.

This means in the round 2, you will pop (0,1) and (1,1) again, and set their distances value as 2.

Now we see our problem:

If the nodes in the queue can be each other’s neighbors, the neighbor can be added to the queue again, which will cause wrong distance.

How to solve it?

distance[i][j] == -1 means this node is unvisited. So before we update node (i,j)’s distance value, check whether distance[i][j] == -1

So we new code is:

Follow-up 2:

If we want to find the minimum path, rather than only find the minimum steps to from one node to another, how to achieve this?
There are two ways:

1. We can store Tuple<Node, Path> into the queue. -> O(n^2)

2. We can use BFS to find how long is the shortest path (assume k). Then we apply DFS to find the path (because we know path length = k, for a path longer than k, we can stop earlier). -> O(n), but DFS has stack overflow problem.

[typical questions]
        [111] Minimum Depth of Binary Tree
        [126] Word Ladder II
        [310] Minimum Height Trees

        [317] Shortest Distance from All Buildings