个人主页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)); queueNode 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; // 扩展下一步注意如果下一步是出口step1 传递 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首次到达即最优效率高判断可达性BFS 或 DFS均可BFS 更快统计所有可能路径数DFS 回溯BFS 无法保留所有路径搜索所有解如八皇后DFS 回溯需要穷举连通块大小 / 洪水填充BFS 或 DFS均可DFS 实现简单简单记忆“最近”、“最少”、“最短”→ 优先考虑 BFS。“所有方案”、“所有路径”、“计数”→ 优先考虑 DFS 回溯。五、拓展思考如果要求统计路径数量假设题目改为“统计从起点到所有出口的不同路径总数”那么 DFS 回溯是唯一选择BFS 无法处理非最短路径因为当路径存在交叉时BFS 的队列顺序是先入先出先到的总是最短的你无法在后续再次处理该节点因为已标记 visited否则会死循环但要注意路径数可能非常大需要用long long甚至大数。若迷宫有环简单路径数有限因为不能重复经过节点DFS 可处理若允许绕圈路径无限则需特殊限制。六、总结算法选择理解 BFS 和 DFS 的本质差异根据问题特性选择合适算法不要惯性用 DFS 解决所有搜索问题。回溯机制DFS 的回溯是穷举路径的基础而 BFS 的“一层层扩展”则天然保证最短路。算法学习不只是刷题更要在错误和思考中总结。希望这篇文章能帮你少踩一些坑更清晰地理解这两种基础搜索算法。如果本文对你有帮助欢迎点赞、收藏、分享。如有疑问请在评论区留言我会尽力解答。博客首发于CSDN转载请注明出处。