BFS深度优先搜索

BFS的定义

BFS(Breadth First Search)，顾名思义就是以广度为优先顺序的搜索算法

矩阵图上的BFS

搜索的bfs其实是图上的bfs类比过来的，先看一道图上BFS的题会比较容易理解

3984 – 迷宫问题

定义一个二维数组：

int maze[5][5] = {
	0, 1, 0, 0, 0,
	0, 1, 0, 1, 0,
	0, 0, 0, 0, 0,
	0, 1, 1, 1, 0,
	0, 0, 0, 1, 0,
};

它表示一个迷宫，其中的1表示墙壁，0表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的最短路线。

如图所示，第一个矩阵是题目中给的矩阵，第二个矩阵是将所有的墙壁转变为#，第三个矩阵则是各个能走的点到起点的距离，我们总是用已经计算出距离的点去推出和他所有相邻的点距离起点的距离，每次都是扩展出相邻的所有点，这个过程体现了BFS搜索中的广度优先

代码实现

const int N = 10;

int n;
int g[N][N];
int dist[N][N];
std::pair<int, int> last[N][N];
std::vector<std::pair<int, int> > ans;

int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};

void bfs() {
    memset(dist, -1, sizeof dist);
    dist[1][1] = 0;
    std::queue<std::pair<int, int> > q;
    q.push({1, 1});

    while (q.size()) {
        std::pair<int, int> t = q.front();
        q.pop();
        int x = t.first, y = t.second;

        for (int i = 0; i < 4; i ++ ) {
            int nx = x + dx[i], ny = y + dy[i];

            if (nx < 1 || nx > n || ny < 1 || ny > n) continue;

            if (g[nx][ny] == 1) continue;
            if (dist[nx][ny] == -1) {
                dist[nx][ny] = dist[x][y] + 1;
                last[nx][ny] = {x, y};
                q.push({nx, ny});
            }
        }
    }
}
void solve() {
    n = 5;
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= n; j ++ ) cin >> g[i][j];

    bfs();
    int x = n, y = n;
    while (last[x][y] != std::make_pair(0, 0)) {
        ans.push_back({x, y});
        std::pair<int, int> t = last[x][y];
        x = t.first, y = t.second;
    }
    ans.push_back({1, 1});

    std::reverse(ans.begin(), ans.end());
    for (int i = 0; i < ans.size(); i ++ ) {
        std::pair<int, int> t = ans[i];
        cout << "(" << t.first - 1 << ", " << t.second - 1 << ")\n";
    }
}

BFS的搜索过程及其与DFS的比较

我们在使用dfs的时候，优先进行的是深度上的搜索，也就是对于每一个搜索树上的节点，我们先去搜索它的儿子节点

而我们bfs则是优先搜索当前节点的兄弟节点

在使用bfs进行暴力枚举的时候，我们将我们所需要枚举的每一种状态看作是一个搜索树上的节点，首先，我们将搜索根节点，其深度为1，然后，我们再去枚举所有的深度为2的节点，也就是所有根节点的儿子节点，接下来，我们再去枚举深度为3的节点，也就是所有的根节点的儿子节点的所有儿子节点，……，直到将所有的叶子节点枚举完毕，这就是我们的bfs的枚举过程

如上图，这是我们在昨天讲dfs的时候枚举排列且$n$等于$4$情况下的搜索树，其中蓝色的数字代表在dfs的时候的搜索顺序，红色的数字代表在bfs的时候的搜索顺序

实现思路

由于我们的枚举过程是一层一层进行的，我们可以用一个队列，存储我们需要去搜索的所有状态，我们从起始状态出发，将起始状态放进队列中，然后取出起始状态，再将起始状态能推出的状态放进队列中，然后再取出队头，将其能推出的所有状态放入队列中，不断迭代，直到所有状态都枚举过了之后，结束我们的搜索。

把状态放在搜索树上看，就是入队顺序和搜索树中的红色节点相同，每次计算完一个状态后，将它加入到队尾。

状态抽象例题

Problem - 1661B - Codeforces

Suppose you have an integer $v$. In one operation, you can:

• either set $v = (v + 1) \bmod 32768$
• or set $v = (2 \cdot v) \bmod 32768$.

You are given $n$ integers $a_1, a_2, \dots, a_n$. What is the minimum number of operations you need to make each $a_i$ equal to $0$?

我们可以把每个数字当成图上的一个点，这个过程是状态的抽象

问题就变成了，从每个点出发，到达$0$这个点需要的步数

而从每个点出发到达$0$这个点的距离和从$0$出发到达各个点距离是相等的

所以我们可以从$0$这个点往后推其他点

每个点都能推出1到3种状态，通过我们的DFS算法去实现即可

代码实现

const int N = 4e4 + 10;
const int P = 32768;

int n;
int a[N];
int dist[N];

void bfs(int s) {
    std::queue<int> q;
    memset(dist, 0x3f, sizeof(dist));
    q.push(s);
    dist[s] = 0;

    while (q.size()) {
        int t = q.front();
        q.pop();

        int v = (t + P - 1) % P;
        if (dist[v] > dist[t] + 1) {
            dist[v] = dist[t] + 1;
            q.push(v);
        }
        if (t % 2 == 0) {
            v = t / 2;
            if (dist[v] > dist[t] + 1) {
                dist[v] = dist[t] + 1;
                q.push(v);
            }
            v = (t + P) / 2;
            if (dist[v] > dist[t] + 1) {
                dist[v] = dist[t] + 1;
                q.push(v);
            }
        }
    }
}