震惊！！！学了这么久的DFS/BFS你都用错了！

个人主页：

<zephyr05>

个人专栏：

<Linux> <C/C++> <竞赛专栏>

座右铭：

等风来不如追风去，追寻的过程就是人生的意义。

目录

一、问题描述

二、题目解析

三、算法对比：DFS 与 BFS 的本质差异

1. BFS 的最优性

2. DFS 的穷举性

3. 关于“交叉路径”的误解

四、什么时候用 DFS，什么时候用 BFS？

五、拓展思考：如果要求统计路径数量？

六、总结

你是否和之前的我一样，学了DFS/BFS的固定套路，每次刷题不管三七二十一就直接按照套路解题，那么恭喜你，读完这篇文章你会对深度优先搜索和广度优先搜索有更本质的认识。

一、问题描述

题目来自某 OJ 平台：题目链接

Kotori 在一个n × m的迷宫中，迷宫最外层被岩浆淹没无法涉足，迷宫内有若干个出口（'e'）。
Kotori 只能上下左右移动，她想知道有多少出口是她能到达的，最近的出口离她有多远？
输入：第一行两个整数n, m(1 ≤ n, m ≤ 30)，随后n行长度为m的字符串，包含'k'（起点）、'.'（道路）、'*'（墙壁）、'e'（出口）。
输出：若有可到达出口，输出两个整数——可选择的出口数量和到达最近出口的步数；否则输出-1。

二、题目解析

这是一道很典型的用BFS可以解决的题目，只要注意考虑充分边界条件。下面给出答案

BFS：

#include <iostream> #include <queue> #include <cstring> using namespace std; const int MAXN = 35; char maze[MAXN][MAXN]; bool vis[MAXN][MAXN]; int n, m; int dx[4] = {0, 0, 1, -1}; int dy[4] = {1, -1, 0, 0}; struct Node { int x, y, step; }; int main() { cin >> n >> m; int sx, sy; for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { cin >> maze[i][j]; if (maze[i][j] == 'k') { sx = i; sy = j; } } } memset(vis, false, sizeof(vis)); queue<Node> q; q.push({sx, sy, 0}); vis[sx][sy] = true; int exitCnt = 0; int minDist = -1; // -1表示尚未找到出口 while (!q.empty()) { Node cur = q.front(); q.pop(); for (int dir = 0; dir < 4; ++dir) { int nx = cur.x + dx[dir]; int ny = cur.y + dy[dir]; // 越界检查 if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue; if (vis[nx][ny]) continue; if (maze[nx][ny] == '*') continue; // 遇到出口 if (maze[nx][ny] == 'e') { exitCnt++; if (minDist == -1) { minDist = cur.step + 1; // BFS首次遇到即为最短 } vis[nx][ny] = true; // 标记，避免重复计数 continue; } // 普通道路 vis[nx][ny] = true; q.push({nx, ny, cur.step + 1}); } } if (exitCnt == 0) { cout << -1 << endl; } else { cout << exitCnt << " " << minDist << endl; } return 0; }

DFS：

#include <iostream> #include <algorithm> using namespace std; const int MAXN = 35; char maze[MAXN][MAXN]; bool visited[MAXN][MAXN]; bool exitVisited[MAXN][MAXN]; // 记录出口是否已经被计数 int n, m; int sx, sy; int exitCnt = 0; int minDist = 0x3f3f3f3f; int dx[4] = {0, 0, -1, 1}; int dy[4] = {-1, 1, 0, 0}; // DFS：当前在 (x, y)，已经走了 step 步 void dfs(int x, int y, int step) { // 如果当前格子是出口 if (maze[x][y] == 'e') { if (!exitVisited[x][y]) { // 第一次到达该出口 exitVisited[x][y] = true; exitCnt++; } minDist = min(minDist, step); // 更新最短距离 return; // 到达出口即停止，不再扩展 } visited[x][y] = true; // 标记当前格子 for (int k = 0; k < 4; ++k) { int nx = x + dx[k]; int ny = y + dy[k]; // 检查边界 if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue; // 不能走：墙壁、已访问 if (maze[nx][ny] == '*') continue; if (visited[nx][ny]) continue; // 扩展下一步（注意：如果下一步是出口，step+1 传递） dfs(nx, ny, step + 1); } visited[x][y] = false; // 回溯，取消标记 } int main() { cin >> n >> m; for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { cin >> maze[i][j]; if (maze[i][j] == 'k') { sx = i; sy = j; } } } dfs(sx, sy, 0); if (exitCnt == 0) { cout << -1 << endl; } else { cout << exitCnt << " " << minDist << endl; } return 0; }

三、算法对比：DFS 与 BFS 的本质差异

虽然 DFS 也能 AC，但我知道 BFS 更适合这类“最短路 + 可达性”问题。为什么？

1. BFS 的最优性

BFS 按层扩展，第一次到达某个节点时一定是最短路径。因此，当 BFS 第一次遇到出口时，其步数就是最短距离，无需继续搜索。每个节点只需入队一次，复杂度 O(n·m)，极其高效。

2. DFS 的穷举性

DFS 会遍历所有可能的简单路径，因此可以找到所有出口，并能更新最短距离（虽然可能多次经过同一个出口）。但代价是时间复杂度可能指数级（在无剪枝的情况下），对于 30×30 的迷宫勉强可行，但若地图更大或路径更多，就会超时。

3. 关于“交叉路径”的误解

我一度困惑：如果两条路径在某个格子交叉，后到的路径会不会因为该格子已被标记而丢失可能性？
答案是否定的——在 BFS 中，先到达的路径一定是最短的，后到的路径不可能提供更优解，因此直接丢弃是正确的。
而在 DFS 中，通过回溯机制，同一个格子可以被多条路径访问（只要路径不重复自身），从而枚举所有可能性。

四、什么时候用 DFS，什么时候用 BFS？

简单记忆：

• “最近”、“最少”、“最短”→ 优先考虑 BFS。

• “所有方案”、“所有路径”、“计数”→ 优先考虑 DFS + 回溯。

五、拓展思考：如果要求统计路径数量？

假设题目改为“统计从起点到所有出口的不同路径总数”，那么 DFS + 回溯是唯一选择，BFS 无法处理非最短路径，因为当路径存在交叉时，BFS 的队列顺序是先入先出，先到的总是最短的，你无法在后续再次处理该节点（因为已标记 visited，否则会死循环）但要注意：

• 路径数可能非常大，需要用long long甚至大数。

• 若迷宫有环，简单路径数有限（因为不能重复经过节点），DFS 可处理；若允许绕圈，路径无限，则需特殊限制。

六、总结

1. 算法选择：理解 BFS 和 DFS 的本质差异，根据问题特性选择合适算法，不要惯性用 DFS 解决所有搜索问题。

2. 回溯机制：DFS 的回溯是穷举路径的基础，而 BFS 的“一层层扩展”则天然保证最短路。

算法学习不只是刷题，更要在错误和思考中总结。希望这篇文章能帮你少踩一些坑，更清晰地理解这两种基础搜索算法。

如果本文对你有帮助，欢迎点赞、收藏、分享。如有疑问，请在评论区留言，我会尽力解答。
博客首发于CSDN，转载请注明出处。