3.8.2. BFS

Breadth first search is a graph traversal algorithm which can efficiently solve single source shortest path problem for unweighted graph. It check the neighbours of the current node and traverses the graph layer by layer.

A normal implementation for BFS is to use a queue to store the neighbours. Take out vertex from the front of the queue, enqueue all its unvisited neighbours into the queue, and mark them as visited by adding them into a visited set or set them in the bitmap.

Another implementation could be use two containers such as queue, vector, list, set etc. Add the source vertex into container A, loop through A and add all the neighbours to B. Then assign B to A, clear B and repeat the previous process. This is used in bi-directional BFS in Section 3.8.9.4.

Also BF-Tree is used to print all the shortest paths from source to destination with predecessor or successor subgraph.

3.8.2.1. Shortest Distance from All Buildings

You want to build a house on an empty land which reaches all buildings in the shortest amount of distance. You can only move up, down, left and right. You are given a 2D grid of values 0, 1 or 2, where:

  • Each 0 marks an empty land which you can pass by freely.

  • Each 1 marks a building which you cannot pass through.

  • Each 2 marks an obstacle which you cannot pass through.

For example, given three buildings at (0,0), (0,4), (2,2), and an obstacle at (0,2):

1 - 0 - 2 - 0 - 1
|   |   |   |   |
0 - 0 - 0 - 0 - 0
|   |   |   |   |
0 - 0 - 1 - 0 - 0

The point (1,2) is an ideal empty land to build a house, as the total travel distance of 3+3+1=7 is minimal. So return 7.

We do BFS multiple times. We change the cell values to know if a cell is visited or not, which make the program more efficient.

(1)- 3 - 2 - 3 - 1        1 - 6 - 2 - 6 -(1)       1 - 9 - 2 - 9 - 1
 |   |   |   |   |        |   |   |   |   |        |   |   |   |   |
 3 - 3 - 3 - 3 - 0   =>   6 - 6 - 6 - 6 - 6   =>   9 - 9 - 9 - 9 - 9
 |   |   |   |   |        |   |   |   |   |        |   |   |   |   |
 3 - 3 - 1 - 3 - 0        6 - 6 - 1 - 6 - 6        9 - 9 -(1)- 9 - 9

A separate distance matrix is used to record the distance of that cell to all the buildings.

 1#include <gtest/gtest.h>
 2#include <sein.hpp>
 3
 4namespace ns_shortest_dist_all {
 5int shortestDistance(vector<vector<int>> &grid) { // TC:O(R*C*X) X - the number of 1 in matrix
 6  int R = grid.size(), C = grid[0].size(), mark = 0, ans;
 7  vector<vector<int>> dist(R, vector<int>(C));
 8  static array<pair<int, int>, 4> dirs = {{{0, 1}, {0, -1}, {1, 0}, {-1, 0}}};
 9  for (int i = 0; i < R; i++)
10    for (int j = 0; j < C; j++)
11      if (grid[i][j] == 1) {
12        vector<pair<int, int>> bfs1={{i,j}}, bfs2;
13        int level = 1;
14        ans = INT_MAX;
15        while (!bfs1.empty()) {
16          for (auto [x, y]: bfs1) {
17            for (auto [dx, dy]: dirs) {
18              int nx = x + dx, ny = y + dy;
19              if (0 <= nx && nx < R && 0 <= ny && ny < C && grid[nx][ny] == mark) {
20                grid[nx][ny] = mark + 3;
21                dist[nx][ny] += level, ans = min(ans, dist[nx][ny]);
22                bfs2.push_back({nx, ny});  // 💣
23              }
24            }
25          }
26          level++;
27          swap(bfs1, bfs2), bfs2.clear();
28        }
29        mark+=3;
30      }
31  return ans == INT_MAX ? -1 : ans;
32}
33}
34using namespace ns_shortest_dist_all;
35TEST(_bfs_shortest_dist_all, a) {
36  vector<vector<int>> grid = {{1, 0, 2, 0, 1},
37                              {0, 0, 0, 0, 0},
38                              {0, 0, 1, 0, 0}};
39  EXPECT_EQ(shortestDistance(grid), 7);
40}