BFS 与 DFS

前言：怎么在一张图里“走遍”所有地方？

想象你在探索一座城堡。城堡里有很多房间，有的房间之间有走廊相连。你想从大厅出发，访问每一个能走到的房间。

两种自然的策略：

• DFS（深度优先搜索）：走进一条走廊就一路走到底，走到死胡同再回头，换另一条路。像走迷宫时贴着右手边走。
• BFS（广度优先搜索）：先把大厅旁边能直接到的房间全走一遍，再去探索这些房间旁边能到的房间……像水波纹一样一层层扩散。

这两种策略都能访问所有可达的房间，但探索的顺序不同。这个顺序的差异非常重要：

• BFS 按距离从近到远展开，所以第一次到达某个房间时，走的一定是最短路径——这就是无权图最短路的解法。
• DFS 一路钻到底再回头，这种”后进先出”的行为天然产生后序遍历——这是拓扑排序的基础。

这篇笔记会分别实现 DFS 和 BFS，对比它们的特性，然后通过一道迷宫最短路的例题展示 BFS 的实际应用。

BFS 与 DFS

问题的本质

给定一个图，从某个起点出发，访问所有可达的节点。两种策略：

• DFS（深度优先）：沿一条路走到头，再回头走另一条。用栈（或递归）实现。
• BFS（广度优先）：先访问近的，再访问远的，逐层展开。用队列实现。

两者的核心区别在于探索的顺序，对应的适用场景也不同。

DFS

vector<int> adj[MAXN];
bool visited[MAXN];

void dfs(int u) {
    visited[u] = true;
    for (int v : adj[u]) {
        if (!visited[v]) dfs(v);
    }
}

递归写法天然就是栈的行为。也可以用显式栈避免递归过深爆栈。

BFS

#include <queue>

vector<int> adj[MAXN];
bool visited[MAXN];
int dist[MAXN];  // 可选：记录距离

void bfs(int start) {
    queue<int> q;
    q.push(start);
    visited[start] = true;
    dist[start] = 0;

    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v : adj[u]) {
            if (!visited[v]) {
                visited[v] = true;
                dist[v] = dist[u] + 1;
                q.push(v);
            }
        }
    }
}

两者对比

特性	DFS	BFS
数据结构	栈（递归）	队列
空间	$O(h)$，$h$ 为递归深度	$O(w)$，$w$ 为最大层宽
最短路（无权图）	❌	✅ 天然按距离展开
拓扑排序	✅ 后序反转	❌
连通性检测	✅	✅
环检测	✅	✅

直觉：DFS 是”钻到底”，适合探索路径结构、生成树、拓扑排序；BFS 是”层层铺开”，适合最短路、层序相关的问题。

例题：走迷宫

给定 $n \times m$ 的网格迷宫，'.' 可走，'#' 是墙。求从左上角 $(1,1)$ 到右下角 $(n,m)$ 的最短步数（只能上下左右移动）。

$1 \le n, m \le 1000$

无权图最短路——BFS 天然解决。

#include <cstdio>
#include <queue>
using namespace std;

const int MAXN = 1001;
char grid[MAXN][MAXN];
int dist[MAXN][MAXN];
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};

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

    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            dist[i][j] = -1;

    queue<pair<int,int>> q;
    q.push({0, 0});
    dist[0][0] = 0;

    while (!q.empty()) {
        auto [x, y] = q.front(); q.pop();
        for (int d = 0; d < 4; d++) {
            int nx = x + dx[d], ny = y + dy[d];
            if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
            if (grid[nx][ny] == '#' || dist[nx][ny] != -1) continue;
            dist[nx][ny] = dist[x][y] + 1;
            q.push({nx, ny});
        }
    }

    printf("%d\n", dist[n - 1][m - 1]);
    return 0;
}

解析：BFS 第一次到达某个节点时，走的就一定是最短路——因为 BFS 按距离从小到大展开，先到的路径不会比后到的长。用 dist 数组同时充当距离记录和访问标记（-1 表示未访问）。四个方向用 dx/dy 数组统一处理，避免写四段重复代码。总时间 $O(nm)$。