搜索 算法

搜索-BFS：广度优先搜索

Avatar photo By froyoisle

知识总结

广度优先搜索（Breadth First Search）

BFS 全称是 Breadth First Search，中文名是宽度优先搜索，也叫广度优先搜索。是图上最基础、最重要的搜索算法之一。

所谓宽度优先。就是每次都尝试访问同一层的节点。 如果同一层都访问完了，再访问下一层。这样做能使 BFS 算法找到的路径是从起点开始的 最短 合法路径。换言之，这条路径所包含的边数最小。在 BFS 结束时，每个节点都是通过从起点到该点的 最短路径 访问的。

DFS vs BFS

小结：DFS 适合于找给定起点到终点的所有解， BFS 适用于找最短路（最优解）。

BFS 的存储实现：队列

思路

  1. 用一个队列 Q 来记录要处理的节点，然后开一个布尔数组 vis[] 来标记是否已经访问过某个节点。
  2. 开始的时候，我们将所有节点的 vis 值设为 0，表示没有访问过；然后把起点 s 放入队列 Q 中并将 vis[] 设为 1。
  3. 之后，我们每次从队列 Q 中取出队首的节点 u，然后把与 u 相邻的所有节点 v 标记为已访问过并放入队列 Q。
  4. 循环直至当队列 Q 为空，表示 BFS 结束。

伪代码

q.push(初始状态); 
while(!q.empty()){ 
    status t = q.front(); // 取队首状态 
    q.pop(); // 队首状态出队 
    for(枚举所有可扩展新状态 v){ 
        if(新状态 v 合法) 
        q.push(v); // 新状态 v 入队 
        // 维护一些必要信息 
    } 
}

在 BFS 的过程中，也可以记录一些额外的信息。例如：

  • 用 d 数组记录起点到某个节点的最短距离（要经过的最少边数），可以方便地得到起点到一个节点的距离。
  • 用 f 数组记录是从哪个节点走到当前节点的，可以方便地还原出从起点到一个点的最短路径。

复杂度

时间复杂度

  总共有 n 个顶点，m 条边要访问，因此时间复杂度是 O(n + m) 。

空间复杂度

    需要标记数组 vis[] 和一个队列，大小为结点数，因此空间复杂度是 O(n)。

应用

  1. 判断地图中各点间的连通性。
  2. 在地图中搜索从给定起点到其他所有点的最短路径。
  3. 在 O(n + m) 时间内求出所有连通块。（从每个没有被访问过的节点开始做 BFS，每次 BFS 会走完一个连通块）。

最短路径类-经典例题

奇怪的电梯

思路

从起点楼层开始 BFS，记录每层楼下一步可达楼层及所需按键次数。

代码-1：DFS（求最短路需剪枝优化）

#include <bits/stdc++.h>
using namespace std;

int n, a, b, k[205], c[205]; 
int e[2] = {-1, 1};

void dfs(int d, int x){ // 当前到达第 d 层，按键次数 x 次 
        c[d] = x; // 数组中记录 
        for(int i = 0; i < 2; i++){
                int t = d + e[i] * k[d];
                if(t >= 1 && t <= n && c[t] > x + 1){ // 仅在可优化时深搜下一步 
                        dfs(t, x + 1);
                }
        }
}

int main(){
        cin >> n >> a >> b;
        for(int i = 1; i <= n; i++){
                cin >> k[i];
        }
        memset(c, 0x7f, sizeof(c));
        dfs(a, 0);
        cout << (c[b] != 0x7f7f7f7f ? c[b] : -1);
        return 0;
}

代码-2：BFS 求线性最短路

#include <bits/stdc++.h>
using namespace std;

int n, a, b, k[205], c[205];
queue<int> q;
void bfs(){
        memset(c, -1, sizeof(c)); // 初始化每层楼状态不可达
        q.push(a); // 起点入队
        c[a] = 0; // 初始化起点 0 次按电梯
        while(!q.empty()){
                int u = q.front(); // 取队首 
                q.pop();
                for(int i = -1; i <= 1; i++){
                        if(!i) continue;
                        int v = u + i * k[u]; // 从 u 出发，下次可达 u-k[u] 或 u+k[u]
                        if(v >= 1 && v <= n && c[v] == -1){ // 边界合法且未访问过 
                                c[v] = c[u] + 1; // u -> v，v 按键次数是 c[u] + 1 
                                q.push(v); // 将楼层 v 入队 
                        }
                }
        } 
        cout << c[b]; // 输出 b 需要的按键次数 
}

int main(){
        cin >> n >> a >> b; 
        for(int i = 1; i <= n; i++){
                cin >> k[i]; 
        }
        bfs();
    return 0; 
}

The Chivalrous Cow B

思路

求给定起点到终点的最短路，用 BFS 即可，输入地图时存入搜索起点坐标和终点坐标。

代码

#include <bits/stdc++.h>
using namespace std;

int n, m, sx, sy, fx, fy, d[155][155];
char mp[155][155];
int b[8][2] = {{-2, -1}, {-2, 1}, {-1, -2}, {-1, 2}, {1, -2}, {1, 2}, {2, -1}, {2, 1}}; 

void bfs(int x, int y){
        queue<int> qx, qy;
        qx.push(x), qy.push(y);
        while(!qx.empty()){
                int xx = qx.front(), yy = qy.front();
                qx.pop(), qy.pop();
                for(int i = 0; i < 8; i++){
                        int x1 = xx + b[i][0], y1 = yy + b[i][1];
                        if(x1 >= 1 && x1 <= n && y1 >= 1 && y1 <= m && mp[x1][y1] != '*' && d[x1][y1] == -1){
                                d[x1][y1] = d[xx][yy] + 1;
                                qx.push(x1), qy.push(y1);
                        }
                }
        }
}

int main(){
        scanf("%d %d\n", &m, &n);
        for(int i = 1; i <= n; i++){
                scanf("%s", mp[i] + 1); // 从 mp[i][1] 开始存 
                for(int j = 1; j <= m; j++){
                        if(mp[i][j] == 'K'){
                                sx = i, sy = j;
                        }
                        if(mp[i][j] == 'H'){
                                fx = i, fy = j;
                        }
                }
        }
        memset(d, -1, sizeof(d));
        d[sx][sy] = 0; // 初始化起点 
        bfs(sx, sy);
        printf("%d", d[fx][fy]);
        return 0; 
}

马的遍历

思路

用队列实现 bfs() 扩展下一步的过程，要注意马的走法，马走日，且八个方向都可扩展。

代码

#include <bits/stdc++.h>
using namespace std;
int n, m, x, y; 
int dis[4005][4005]; // dis[x][y] 存起点到 (x, y)最短路径的距离
int b[8][2] = {{1, 2}, {1, -2}, {-1, 2}, {-1, -2},
                                {2, 1}, {2, -1}, {-2, 1}, {-2, -1}}; // 8 个扩展方向 
queue<int> qx, qy;                                
void bfs(){
        memset(dis, -1, sizeof(dis)); // 每个字节都赋值 (11111111) ,即数组初始化为 -1
        qx.push(x); qy.push(y); // 初始状态入队
        dis[x][y] = 0; // 初始距离为 0
        while(!qx.empty()){
                int tx = qx.front(), ty = qy.front(); // 取坐标值 
                qx.pop(); qy.pop(); // 访问过状态出队
                for(int i = 0; i < 8; i++){ // 扩展由 tx, ty 出发的下一步 
                        int x1 = tx + b[i][0], y1 = ty + b[i][1];
                        if(x1 >= 1 && x1 <= n && y1 >= 1 && y1 <= m && dis[x1][y1] == -1){ // 未越界且未访问过的下一步 
                                qx.push(x1); qy.push(y1); // 新状态入队 
                                dis[x1][y1] = dis[tx][ty] + 1;  // 更新下一步距离
                        }
                } 
        }        
} 
int main(){
        cin >> n >> m >> x >> y;
         bfs();
        for(int i = 1; i <= n; i++){
                for(int j = 1; j <= m; j++){
                        printf("%-5d", dis[i][j]);  // 左对齐 5 个场宽 
                }
                printf("\n");
        } 
    return 0;
}

迷宫问题（打印最短路）

思路

在访问到每个结点时记录它的父节点信息，遍历路径时先从终点开始倒推将经过结点入栈，最后从栈顶起点开始输出。

代码

#include <bits/stdc++.h>
#define maxn 10
using namespace std;

int a[maxn][maxn], d[maxn][maxn], f[maxn][maxn][2]; // f[i][j] 记录父节点 
int b[4][2] = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}}; // 上左下右

void bfs(){
        d[0][0] = 0; // 起点距离初始化 
    queue<int> qx, qy;
    qx.push(0), qy.push(0);
    while(!qx.empty()){
        int xx = qx.front(), yy = qy.front();
        qx.pop(), qy.pop();
        for(int i = 0; i < 4; i++){
            int x1 = xx + b[i][0], y1 = yy + b[i][1];
            if(x1 >= 0 && x1 <= 4 && y1 >= 0 && y1 <= 4 && !a[x1][y1] && d[x1][y1] == -1){
                d[x1][y1] = d[xx][yy] + 1; // (xx, yy) -> (x1, y1)
                f[x1][y1][0] = xx, f[x1][y1][1] = yy; // 记录 (x1, y1) 的父节点 (xx, yy) 
                qx.push(x1), qy.push(y1);
            }
        }        
    }
}

void prt(){
        stack<int> sx, sy;
        int x = 4, y = 4;
        while(x || y){ // 没到起点 (0, 0) 
                sx.push(x), sy.push(y);
                int tx = sx.top(), ty = sy.top();
                x = f[tx][ty][0], y = f[tx][ty][1];
        }
        sx.push(0), sy.push(0); // 起点放栈顶 
        while(!sx.empty()){
                printf("(%d, %d)\n", sx.top(), sy.top());
                sx.pop(), sy.pop();
        }
}
int main(){
    for(int i = 0; i < 5; i++){
            for(int j = 0; j < 5; j++){
            scanf("%d", &a[i][j]);
        }
    }
    memset(d, -1, sizeof(d)); // 初始化距离数组 -1 表示未访问
    bfs();
    prt();
    return 0; 
}

连通性求解类-经典例题

入门

思路

求给定起点所在连通块的元素个数，从给定点开始 bfs 即可。

代码

#include <bits/stdc++.h>
using namespace std;
int h, w, s, sx, sy;
int b[4][2] = {{0, -1}, {-1, 0}, {0, 1}, {1, 0}};
char a[55][55];

int bfs(int x, int y){ 
        queue<int> qx, qy;
        qx.push(x), qy.push(y);
        s++; // 初始黑色瓷砖算上 
        while(!qx.empty()){
                int x1 = qx.front(), y1 = qy.front();
                qx.pop(), qy.pop();
                for(int i = 0; i < 4; i++){
                        int x2 = x1 + b[i][0], y2 = y1 + b[i][1];
                        if(x2 >= 1 && x2 <= h && y2 >= 1 && y2 <= w && a[x2][y2] == '.'){
                                qx.push(x2), qy.push(y2);
                                s++;
                                a[x2][y2] = ' ';
                        }
                }
        }
        return s;
}

int main(){
        scanf("%d %d", &w, &h);
        for(int i = 1; i <= h; i++){
                for(int j = 1; j <= w; j++){
                        cin >> a[i][j];
                        if(a[i][j] == '@'){
                                sx = i, sy = j;
                        }
                }
        }
        printf("%d", bfs(sx, sy));
        return 0;
}

01迷宫

思路

求解给定坐标所在连通块的元素个数，如果询问坐标点还未搜索过所在连通块，以该点作为起点进行 bfs，同步计数连通块个数，否则直接输出之前搜索过程中标记的连通块及其个数。

代码

#include <bits/stdc++.h>
using namespace std;

// f[][] 记录所在连通块, ans[] 记录连通块元素个数 
int n, m, x, y, s, f[1005][1005], ans[1000005]; 
char a[1005][1005];
int d[4][2] = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}};

void bfs(int x, int y){
        if(f[x][y]){
                printf("%d\n", ans[f[x][y]]);
                return;
        }
        queue<int> qx, qy;
        qx.push(x), qy.push(y);
        s++; // s 记录是第几个连通块 
        f[x][y] = s; // 标记起点连通块编号 
        int cnt = 1;  // 计数该连通块元素个数 
        while(!qx.empty()){
                int x0 = qx.front(), y0 = qy.front();
                qx.pop(), qy.pop();
                for(int i = 0; i < 4; i++){
                        int x1 = x0 + d[i][0], y1 = y0 + d[i][1];
                        if(abs(a[x1][y1] - a[x0][y0]) == 1 && !f[x1][y1]){
                                qx.push(x1), qy.push(y1);
                                f[x1][y1] = s; // 标记该点的连通块编号 
                                cnt++; // 该连通块计数加 1 
                        }
                }        
        }
        ans[s] = cnt;
        printf("%d\n", cnt);
}

int main(){
        scanf("%d %d", &n, &m);
        for(int i = 1; i <= n; i++){
                scanf("%s", a[i] + 1); // 从 a[i][1] 开始存 
        }
        while(m--){
                scanf("%d %d", &x, &y);
                bfs(x, y);
        }
        return 0;
}

填涂颜色

思路

正面寻找闭合圈内的 0 可能不太好找，可以从反面，将与边界相连的 0 标记为 “非闭合圈” 0 的状态，比如用 -1 标记。这样就可以从 (0, 0) 开始搜索与边界相连的所有“非闭合圈” 0，进行标记染色，最后矩阵中剩下未染色的 0 就是闭合圈中的 0。输出时进行分支判断即可。

代码

#include <bits/stdc++.h>
#define maxn 105
using namespace std;

int n, a[maxn][maxn];
int d[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
queue<int> qx, qy;
void bfs(int x, int y){
        a[x][y] = -1; // 标记起点
        qx.push(x), qy.push(y);
        while(!qx.empty()){
                int x1 = qx.front(), y1 = qy.front();
                qx.pop(), qy.pop();
                for(int i = 0; i < 4; i++){
                        int x2 = x1 + d[i][0], y2 = y1 + d[i][1];
                        if(x2 >= 0 && x2 <= n + 1 && y2 >= 0 && y2 <= n + 1 && !a[x2][y2]){
                                qx.push(x2), qy.push(y2);
                                a[x2][y2] = -1; // 特殊标记 
                        }
                }
        }

}

int main(){
        cin >> n;
        for(int i = 1; i <= n; i++){
                for(int j = 1; j <= n; j++){
                        cin >> a[i][j];
                }
        } 
        bfs(0, 0); // (0, 0) 开始连通的 0 不属于闭合圈，将这块找到标记为 -1 
        for(int i = 1; i <= n; i++){
                for(int j = 1; j <= n; j++){
                        if(a[i][j] == 0) cout << 2 << " ";
                        else if(a[i][j] == -1) cout << 0 << " "; 
                        else cout << a[i][j] << " ";
                }
                cout << "\n";
        }
    return 0;
}

拓展习题

Meteor Shower S

思路

首先预处理每个位置被流星烧焦的最早时间，然后从 (0, 0) 开始 bfs 每个点的到达时间，如果到达时间小于该点被烧焦时间，即为可达点，更新到达时间，找出所有可到达的点。

最后遍历每个点，在左右可到达的点中找到最早的一个安全点（不会被流星烧焦的点），记录最早时间，如果找不到就是不存在安全位置。

代码

#include <bits/stdc++.h>
using namespace std;

int m, x, y, t, d[310][310], a[310][310], ans = INT_MAX; 
int b[5][2] = {{0, 0}, {-1, 0}, {0, -1}, {1, 0}, {0, 1}};
queue<int> qx, qy;

int main(){
        memset(d, 0x7f, sizeof(d));
        scanf("%d ", &m);
        while(m--){ 
                scanf("%d %d %d", &x, &y, &t);
                for(int i = 0; i <= 4; i++){
                        int x1 = x + b[i][0], y1 = y + b[i][1];
                        if(x1 >= 0 && y1 >= 0)
                                d[x1][y1] = min(d[x1][y1], t);
                }
        }
        memset(a, -1, sizeof(a));
        a[0][0] = 0;
        qx.push(0), qy.push(0);
        while(!qx.empty()){
                int xx = qx.front(), yy = qy.front();
                qx.pop(), qy.pop();
                for(int i = 1; i <= 4; i++){
                        int x1 = xx + b[i][0], y1 = yy + b[i][1];
                        if(x1 >= 0 && y1 >= 0 && a[x1][y1] == -1 && a[xx][yy] + 1 < d[x1][y1]){
                                                a[x1][y1] = a[xx][yy] + 1;
                                                qx.push(x1), qy.push(y1);
                        }
                }
        }
        for(int i = 0; i < 305; i++){
                for(int j = 0; j < 305; j++){
                        if(a[i][j] != -1 && d[i][j] == 0x7f7f7f7f){ // 可到达的不会有流星的点 
                                ans = min(ans, a[i][j]); 
                        }
                } 
        }
        if(ans == INT_MAX){
                printf("-1");
        }
        else{
                printf("%d", ans);
        }
        return 0;
}

最后的迷宫

思路

本题的二维行列坐标需要降维才能存储下。

代码

#include <bits/stdc++.h>
using namespace std;

int n, m, ans, dis[16500]; // dis[i]：对降维后的坐标 i， 哈利需要 dis[i] 步能到该点 
int hx, hy, jx, jy;
char a[16500], b[16500]; // b[] 用来标记哪些位置能看到奖杯 
const int d[8][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0},
                                         {1, 1}, {1, -1}, {-1, 1}, {-1, -1}};

int c(int x, int y){ // 把二维矩阵坐标转成一维 (i, j) -> (i-1) * m + j 
        return (x-1) * m + y; 
}

void bfs(){
        memset(dis, -1, sizeof(dis)); // 每次搜索前重新初始化距离数组 
        queue<int> qx, qy;
        qx.push(hx), qy.push(hy); // 哈利坐标入队
        dis[c(hx, hy)] = 0; // 起始点距离为 0 
        while(!qx.empty()){
                int x = qx.front(), y = qy.front(); // 取队首坐标 
                qx.pop(), qy.pop(); // 弹出队首坐标 
                if(b[c(x, y)] == 'Y') { // 若该处能看到奖杯 
                        ans = dis[c(x, y)]; // 搜索到的最短路就是答案 
                        return;
                }
                for(int i = 0; i < 4; i++){ // 遍历 (x, y) 的四个方向 
                        int x1 = x + d[i][0], y1 = y + d[i][1];
                        if(x1 >= 1 && x1 <= n && y1 >= 1 && y1 <= m  // 未越界 
                                && dis[c(x1, y1)] == -1 && b[c(x1, y1)] != 'X'){ // 未去过的空地
                                dis[c(x1, y1)] = dis[c(x, y)] + 1; // 更新距离
                                qx.push(x1), qy.push(y1); // 新坐标入队 
                        }                 
                }
        }         
}
int main(){
        cin >> n >> m;
        for(int i = 1; i <= n * m; i++)
                cin >> a[i];
        while(cin >> jx >> jy >> hx >> hy){
                if(!hx && !hy && !jx && !jy)
                        break;
                memcpy(b, a, sizeof(a));
                b[c(jx, jy)] = 'Y'; // 奖杯 & 能看到奖杯的位置，都标成 Y
                // 遍历奖杯周围的八个方向，标记能看到奖杯的位置
                for(int i = 0; i < 8; i++){
                        int x1 = jx + d[i][0], y1 = jy + d[i][1]; // 下个位置
                        while(x1 >= 1 && x1 <= n && y1 >= 1 && y1 <= m && b[c(x1, y1)] == 'O') { // 该方向望到头 
                                b[c(x1, y1)] = 'Y'; // 可以看到
                                x1 += d[i][0], y1 += d[i][1]; // 该方向下一步 
                        }
                }
                ans = -1; // 搜索前重新初始化答案 
                bfs();
                if(ans != -1) cout << ans << "\n";
                else cout << "Poor Harry\n";
        }
        return 0;
}

拓展资料

  1. OI-Wiki：BFS（图论）
  2. 洛谷题单：【算法1-7】搜索
  3. POJ-NOI：2.5基本算法之搜索
Avatar photo

By froyoisle

Related Post

并查集 算法

并查集

Avatar photofroyoisle
STL 算法

STL标准库（三）：算法篇

Avatar photofroyoisle
STL 算法

STL标准库（二）：关联式容器

Avatar photofroyoisle

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

You Missed

心理 生活 读书

《隐藏的自我》读书笔记

并查集 算法

并查集

NOIP/CSP 普及组 复赛 真题

2002-NOIP-普及组：复赛真题及解析

反思 生活 读书

《幸福超越完美》读书笔记