BFS 广度优先搜索算法简介 – 以平面网格为例

广度优先搜索算法 (BFS, Breadth First Search) 是一种寻找最短路径的方法。与深度优先算法 (DFS) 相比，BFS 的时间复杂度低不少，但空间复杂度大很多。

BFS 的核心理念是每次都尝试访问同一层的节点，直到同一层的节点都访问完，再进入下一层。

(这个) 算法过程可以看做是图上火苗传播的过程：最开始只有起点着火了，在每一时刻，有火的节点都向它相邻的所有节点传播火苗。（OI Wiki）

1. BFS 原理

以平面网格为例，每一个网格都相当于图中的一个节点，每个节点都与其右、下、左、上四个方向的节点相连。

如图是一个 3*3 的平面网格，其 (1, 1) 点为起点，(3, 3) 点为终点，我们要通过 BFS 算法寻找两点之间的最短路径。

首先，我们按照“右、下、左、上”的顺序进行搜索，每探测一个点，就标记一个数字。这个探测顺序并不是固定的，只要能够完整地探测到所有的同级节点即可。探测的顺序不同，程序最后得到的路径可能不同。但无论如何，路径所需的步数一定是相同的，均为最少步数。

首先我们为起点标序号“1”，按照我们约定的顺序“右、下、左、上”进行探测。为“1”右侧的节点标“2”，下方的节点标“3”，其左侧和上方没有节点。至此我们就完成了对“1”的所有标记。

接着，按照标号的顺序，对“2”节点重复这个操作，为其右侧节点标“4”，下方节点标“5”，其左侧已有标记，上方没有节点。

继续对“3”重复这个操作，其右侧已有标记，为下方节点标“6”，左侧没有节点，上方已有标记。

重复这个过程，对“4、5、6 ······ k”进行探测和标记，直到标记了所有的节点。

这个树状图表示了我们刚刚进行的所有操作。我们从起点 (1, 1) 开始探测，在 (1, 1) 的周围发现了 (1, 2) 和 (2, 1)；接着在 (1, 2) 周围探测，发现了 (1, 3) 和 (2, 2) ······

从这个树状图，我们可以很容易地发现从起点 (1, 1) 到终点 (3, 3) 的一条路径，也就是最左侧的这条路径，如图所示。

显然这条路径虽然不唯一，但确实是最短路径中的一条。读者可以尝试改变探测顺序，看看会得到怎样的一条路径，步数是否一致。

2. 代码实现思路

通过树形图，我们可以一眼看出路径，但是我们要通过代码找出最短路径。

我们的整个探测过程可以写成一个二维数组，就像一个个节点排成了一个队列。

刚才，我们从序号为“1”的节点，也就是起点开始依次探测，直到探测到了终点。可以使用一个变量 head 来表示探测进度，这个数据可以让程序知道该探测哪个节点。

除了要知道探测哪个节点，也要知道探测结果往哪里存放，所以我们还需要另一个变量 tail。

最初，head 和 tail 两个变量都指向位置 1，按照约定的顺序“右、下、左、上”探测其可访问位置。

先是右边，判断发现右侧节点可访问，所以 tail 变量移动一位，记录坐标 (1, 2)；然后是下方，判断发现下方节点可访问，所以 tail 再移动一位，记录坐标 (2, 1)。其左侧和上方的位置不可访问，所以此时 (1, 1) 点的所有可访问位置已经探测和记录完毕，所以将 head 变量向下移动一位，以此类推，直到找到终点。

若在 head > tail ，即 head 变量已经超过 tail 时，还没有发现终点，则表明从给定的起点到终点间不存在通路。

这是刚才的过程的另一个视角。

刚才，我们找出最短路径的方法是观察树形图，但是程序没有这样的瞪眼能力。如果我们把最短路径经过的节点都标记出来，是这样的：

我们注意到，可以给这个二维数组增加一个第三列，记录每个节点的来源点，也就是“该节点是在探测哪个节点的时候发现的”。我们只需要在第三列记录当该点被记录时的 head 的值。

现在，只需要从终点开始回溯，就可以复原完整的路径了。例如 (3, 3) 点来自标号为“7”的点，也就是 (2, 3)； (2, 3) 点来自标号为“4”的点，也就是 (1, 3)。这说明路径中存在 ··· -> (1, 3) -> (2, 3) -> (3, 3) ，以此类推我们就能复原整条路径了。

三、平面网格 (迷宫) 的 BFS 寻路程序

我们用 C 写一个适用于平面网格（也就是迷宫）的 BFS 寻路程序。原理都一样，无论什么语言差别都不大。

迷宫 BFS 的核心逻辑就是：

从起点入队
while 队列不空:
    取出当前位置
    枚举上下左右四个方向
    if (新位置合法 && 不是墙 && 没访问过):
        标记访问
        更新距离
        入队

从起点入队
while 队列不空:
    取出当前位置
    枚举上下左右四个方向
    if (新位置合法 && 不是墙 && 没访问过):
        标记访问
        更新距离
        入队

我们在梳理思路的时候，还没有考虑如何遍历四个方向、如何判断一个位置“合法 && 不是墙 && 没访问过”等等，所以我们现在来考虑这些问题。

#include <stdio.h>

#define MAXN 105

int n, m;
char grid[MAXN][MAXN];

int visited[MAXN][MAXN];

// q[i][0] = x
// q[i][1] = y
// q[i][2] = 前一个点在队列中的下标
int q[MAXN * MAXN][3];

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

int bfs(int sx, int sy, int tx, int ty) {
    int front = 0;
    int rear = 0;

    // 起点入队
    q[rear][0] = sx;
    q[rear][1] = sy;
    q[rear][2] = -1;   // 起点没有来源
    rear++;

    visited[sx][sy] = 1;

    while (front < rear) {
        // cur 是当前点在队列中的下标
        int cur = front;

        int x = q[cur][0];
        int y = q[cur][1];
        front++;

        // 如果当前点就是终点，返回它在队列中的下标
        if (x == tx && y == ty) {
            return cur;
        }

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

            if (nx < 0 || nx >= n || ny < 0 || ny >= m) {
                continue;
            }

            if (grid[nx][ny] == '#') {
                continue;
            }

            if (visited[nx][ny]) {
                continue;
            }

            visited[nx][ny] = 1;

            // 新点入队
            q[rear][0] = nx;
            q[rear][1] = ny;

            // 关键：记录新点是从 cur 这个队列位置来的
            q[rear][2] = cur;

            rear++;
        }
    }

    // 没找到终点
    return -1;
}

void printPath(int targetIndex) {
    int path[MAXN * MAXN][2];
    int len = 0;

    int cur = targetIndex;

    // 沿着 q[cur][2] 一直往前找
    while (cur != -1) {
        path[len][0] = q[cur][0];
        path[len][1] = q[cur][1];
        len++;

        cur = q[cur][2];
    }

    // 反向输出
    for (int i = len - 1; i >= 0; i--) {
        printf("(%d, %d)", path[i][0], path[i][1]);

        if (i != 0) {
            printf(" -> ");
        }
    }

    printf("\n");

    // 路径中有 len 个点，所以步数是 len - 1
    printf("最短步数：%d\n", len - 1);
}

int main() {
    int sx, sy, tx, ty;

    scanf("%d %d", &n, &m);

    for (int i = 0; i < n; i++) {
        scanf("%s", grid[i]);
    }

    scanf("%d %d %d %d", &sx, &sy, &tx, &ty);

    int targetIndex = bfs(sx, sy, tx, ty);

    if (targetIndex == -1) {
        printf("无法到达\n");
    } else {
        printf("路径：");
        printPath(targetIndex);
    }

    return 0;
}

#include <stdio.h>

#define MAXN 105

int n, m;
char grid[MAXN][MAXN];

int visited[MAXN][MAXN];

// q[i][0] = x
// q[i][1] = y
// q[i][2] = 前一个点在队列中的下标
int q[MAXN * MAXN][3];

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

int bfs(int sx, int sy, int tx, int ty) {
    int front = 0;
    int rear = 0;

    // 起点入队
    q[rear][0] = sx;
    q[rear][1] = sy;
    q[rear][2] = -1;   // 起点没有来源
    rear++;

    visited[sx][sy] = 1;

    while (front < rear) {
        // cur 是当前点在队列中的下标
        int cur = front;

        int x = q[cur][0];
        int y = q[cur][1];
        front++;

        // 如果当前点就是终点，返回它在队列中的下标
        if (x == tx && y == ty) {
            return cur;
        }

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

            if (nx < 0 || nx >= n || ny < 0 || ny >= m) {
                continue;
            }

            if (grid[nx][ny] == '#') {
                continue;
            }

            if (visited[nx][ny]) {
                continue;
            }

            visited[nx][ny] = 1;

            // 新点入队
            q[rear][0] = nx;
            q[rear][1] = ny;

            // 关键：记录新点是从 cur 这个队列位置来的
            q[rear][2] = cur;

            rear++;
        }
    }

    // 没找到终点
    return -1;
}

void printPath(int targetIndex) {
    int path[MAXN * MAXN][2];
    int len = 0;

    int cur = targetIndex;

    // 沿着 q[cur][2] 一直往前找
    while (cur != -1) {
        path[len][0] = q[cur][0];
        path[len][1] = q[cur][1];
        len++;

        cur = q[cur][2];
    }

    // 反向输出
    for (int i = len - 1; i >= 0; i--) {
        printf("(%d, %d)", path[i][0], path[i][1]);

        if (i != 0) {
            printf(" -> ");
        }
    }

    printf("\n");

    // 路径中有 len 个点，所以步数是 len - 1
    printf("最短步数：%d\n", len - 1);
}

int main() {
    int sx, sy, tx, ty;

    scanf("%d %d", &n, &m);

    for (int i = 0; i < n; i++) {
        scanf("%s", grid[i]);
    }

    scanf("%d %d %d %d", &sx, &sy, &tx, &ty);

    int targetIndex = bfs(sx, sy, tx, ty);

    if (targetIndex == -1) {
        printf("无法到达\n");
    } else {
        printf("路径：");
        printPath(targetIndex);
    }

    return 0;
}

#include <stdio.h>

// 地图最大尺寸 100*100，为防止越界，可将限制设得稍大一些
#define MAXN 105

int n, m;                 // 地图的长和宽
char grid[MAXN][MAXN];    // 记录迷宫地图
int visited[MAXN][MAXN];  // 记录已访问过的位置，为 1 表示访问过，为 0 表示未访问过
int dist[MAXN][MAXN];     // 记录起点到某点的最短距离

#include <stdio.h>

// 地图最大尺寸 100*100，为防止越界，可将限制设得稍大一些
#define MAXN 105

int n, m;                 // 地图的长和宽
char grid[MAXN][MAXN];    // 记录迷宫地图
int visited[MAXN][MAXN];  // 记录已访问过的位置，为 1 表示访问过，为 0 表示未访问过
int dist[MAXN][MAXN];     // 记录起点到某点的最短距离

我们可以向 grid[x][y] 这个数组中存入地图，例如用 . 表示可访问位置，用 # 表示障碍物。

// 示例地图数据
....
.#..
.#..
....

// 读入之后就是：
grid[0] = "....";
grid[1] = ".#..";
grid[2] = ".#..";
grid[3] = "....";

// 示例地图数据
....
.#..
.#..
....

// 读入之后就是：
grid[0] = "....";
grid[1] = ".#..";
grid[2] = ".#..";
grid[3] = "....";

// q[i][0] 表示第 i 个点的 x 坐标
// q[i][1] 表示第 i 个点的 y 坐标
// q[i][2] 表示第 i 个点的来源点序号
int q[MAXN * MAXN][3];

// q[i][0] 表示第 i 个点的 x 坐标
// q[i][1] 表示第 i 个点的 y 坐标
// q[i][2] 表示第 i 个点的来源点序号
int q[MAXN * MAXN][3];

我们用一个二维数组来模拟队列。因为迷宫是一个二维平面，所以队列的每个元素（也就是二维数组的每一行）都要存入两个数，分别表示横纵坐标；为了记录路径，还要存入第三个数，表示该点的上一个点。

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

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

我们用这两个数组来表示四个方向：

// 若当前点为 (x, y)，那么我们要探测的点就可以这样表示：
nx = x + dx[i];
ny = y + dy[i];

// 例如，右侧点即为：
nx = 2 + 0 = 2;
ny = 3 + 1 = 4;

// 要对四个方向进行探测，只需要遍历 i 从 0 到 3 即可

// 若当前点为 (x, y)，那么我们要探测的点就可以这样表示：
nx = x + dx[i];
ny = y + dy[i];

// 例如，右侧点即为：
nx = 2 + 0 = 2;
ny = 3 + 1 = 4;

// 要对四个方向进行探测，只需要遍历 i 从 0 到 3 即可

void bfs(int sx, int sy, int tx, int ty) {
    // 初始时，队列为空
    int head = 0;
    int tail = 0;
    
    q[tail][0] = sx;
    q[tail][1] = sy;
    q[tail][2] = -1;      // 起点没有来源，我们设置为 -1
    tail++;
    
    visited[sx][sy] = 1;  // 将起点设置为已探测过的点

void bfs(int sx, int sy, int tx, int ty) {
    // 初始时，队列为空
    int head = 0;
    int tail = 0;
    
    q[tail][0] = sx;
    q[tail][1] = sy;
    q[tail][2] = -1;      // 起点没有来源，我们设置为 -1
    tail++;
    
    visited[sx][sy] = 1;  // 将起点设置为已探测过的点

完成了上述准备工作后，我们终于可以开始写 BFS 函数了。

参数 sx, sy 表示 BFS 的起始位置，tx, ty 表示终点位置。例如我们如果在主函数中调用 bfs(0, 0, 3, 3); 就表示搜索一个 3*3 迷宫中从左上角到右下角的一条最短路径，也就是我们之前演示的例子。

然后，在开始之前，令起点入队，并将起点标记为已访问过的点。

while (head < tail) {
    // 先取出当前点坐标
    int cur_head = head;
    int x = q[cur_head][0];
    int y = q[cur_head][1];
    head++;
    
    if (x == tx && y == ty) return cur_head; // 如果到达终点，直接返回来源

while (head < tail) {
    // 先取出当前点坐标
    int cur_head = head;
    int x = q[cur_head][0];
    int y = q[cur_head][1];
    head++;
    
    if (x == tx && y == ty) return cur_head; // 如果到达终点，直接返回来源

只要 head 还小于 tail，就让搜搜继续。取出当前 head 点，先判断是否到达终点。若已经到达终点，就终止函数，并返回终点的来源，这样就可以通过回溯确认整个队列。

    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        
        // 判断位置是否合法
        if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue; // 不在迷宫内
        if (grid[nx][ny] == '#') continue;                    // 有障碍
        if (visited[nx][ny]) continue;                        // 已经访问过
        
        // 新点入队
        visited[nx][ny] = 1;
        
        q[tail][0] = nx;
        q[tail][1] = ny;
        q[tail][2] = cur_head;  // 记录来源
        
        tail++;
    }
}

    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        
        // 判断位置是否合法
        if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue; // 不在迷宫内
        if (grid[nx][ny] == '#') continue;                    // 有障碍
        if (visited[nx][ny]) continue;                        // 已经访问过
        
        // 新点入队
        visited[nx][ny] = 1;
        
        q[tail][0] = nx;
        q[tail][1] = ny;
        q[tail][2] = cur_head;  // 记录来源
        
        tail++;
    }
}

从当前点 (x, y) 出发，尝试向四个方向走，新的位置是 (nx, ny)。

得到新的位置后，依次判断该位置是否满足要求。若所有要求全部满足，则将新点入队，并记录新点的来源。至此整个 while 循环结束。

return -1

return -1

若直到 head 已经大于 tail，仍没有触发 return，也就是仍未找到终点，说明给定的起点和终点间不存在通路，返回 -1.

void printPath(int targetIndex) {
    int path[MAXN * MAXN][2];
    int len = 0;

    int cur = targetIndex;

    // 沿着 q[cur][2] 一直往前找
    while (cur >= 0) {
        path[len][0] = q[cur][0];
        path[len][1] = q[cur][1];
        len++;

        cur = q[cur][2];
    }

    // 反向输出
    for (int i = len - 1; i >= 0; i--) {
        printf("(%d, %d)", path[i][0], path[i][1]);

        if (i != 0) {
            printf(" -> ");
        }
    }

    printf("\n");

    // 路径中有 len 个点，所以步数是 len - 1
    printf("最短步数：%d\n", len - 1);
}

void printPath(int targetIndex) {
    int path[MAXN * MAXN][2];
    int len = 0;

    int cur = targetIndex;

    // 沿着 q[cur][2] 一直往前找
    while (cur >= 0) {
        path[len][0] = q[cur][0];
        path[len][1] = q[cur][1];
        len++;

        cur = q[cur][2];
    }

    // 反向输出
    for (int i = len - 1; i >= 0; i--) {
        printf("(%d, %d)", path[i][0], path[i][1]);

        if (i != 0) {
            printf(" -> ");
        }
    }

    printf("\n");

    // 路径中有 len 个点，所以步数是 len - 1
    printf("最短步数：%d\n", len - 1);
}

path 用来保存路径上的每一个坐标。len 表示路径长度，也就是路径中有多少个点。

int main() {
    int sx, sy, tx, ty;

    scanf("%d %d", &n, &m);

    for (int i = 0; i < n; i++) {
        scanf("%s", grid[i]);
    }

    scanf("%d %d %d %d", &sx, &sy, &tx, &ty);

    int targetIndex = bfs(sx, sy, tx, ty);

    if (targetIndex == -1) {
        printf("无法到达\n");
    } else {
        printf("路径：");
        printPath(targetIndex);
    }

    return 0;
}

int main() {
    int sx, sy, tx, ty;

    scanf("%d %d", &n, &m);

    for (int i = 0; i < n; i++) {
        scanf("%s", grid[i]);
    }

    scanf("%d %d %d %d", &sx, &sy, &tx, &ty);

    int targetIndex = bfs(sx, sy, tx, ty);

    if (targetIndex == -1) {
        printf("无法到达\n");
    } else {
        printf("路径：");
        printPath(targetIndex);
    }

    return 0;
}

以下是两个输入和输出样例：

输入样例1：
3 3
...
.#.
.#.
0 0 2 2

输出样例1：
路径：(0,0) -> (1,0) -> (2,0) -> (2,1) -> (2,2)
最短步数：4

输入样例1：
4 4
...#
..#.
.#..
#...
1 1 2 2

输出样例1：
无法到达

输入样例1：
3 3
...
.#.
.#.
0 0 2 2

输出样例1：
路径：(0,0) -> (1,0) -> (2,0) -> (2,1) -> (2,2)
最短步数：4

输入样例1：
4 4
...#
..#.
.#..
#...
1 1 2 2

输出样例1：
无法到达

至此，整个 BFS 示例程序都介绍完毕了。