【算法】什么是 DFS 与 BFS 及他们的区别
博主介绍：✌全网粉丝24W+，CSDN博客专家、Java领域优质创作者，掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域✌
技术范围：SpringBoot、SpringCloud、Vue、SSM、HTML、Nodejs、Python、MySQL、PostgreSQL、大数据、物联网、机器学习等设计与开发。
感兴趣的可以先关注收藏起来，在工作中、生活上等遇到相关问题都可以给我留言咨询，希望帮助更多的人。
技术扩展：最近发现了一个特别好用的人工智能学习网站，通俗易懂，风趣幽默，忍不住想分享一下给大家，进入传送门：https://www.captainbed.cn/no8g/。
什么是 DFS 与 BFS 及他们的区别
- 一、概念介绍
- 二、DFS 深度优先搜索
- 三、BFS 广度优先搜索
- 四、核心区别对比表
- 五、通俗比喻
- 六、选型建议
一、概念介绍
DFS 和 BFS
DFS：深度优先搜索（Depth‑First Search）
BFS：广度优先搜索（Breadth‑First Search）
二者都是图 / 树的遍历算法，用于访问图、树上所有节点。
二、DFS 深度优先搜索
思想：一条路走到黑，走不通再回头回溯
优先往深处走，直到不能继续，再回退到上一个分叉，走另一条分支。
- 实现方式
- 递归（系统栈），代码简洁
- 手动栈 Stack，避免递归栈溢出
- 访问顺序：尽可能往下，再回溯
伪代码（递归 DFS）
defdfs(node):标记node已访问for每个邻接节点next_node:if未访问:dfs(next_node)DFS 例子（树）
A /\B C / DDFS 遍历：A → B → D → C
三、BFS 广度优先搜索
思想：一层一层向外扩散，先访问离起点近的
先访问起点的所有直接邻居，再访问邻居的邻居，一层一层遍历。
实现方式：队列 Queue，先进先出
特点：按距离起点远近顺序访问，第一次到达某节点就是最短路径（无权图）
伪代码
queue=[start]标记start已访问whilequeue不为空:node=出队for每个邻接节点next_node:if未访问:标记访问 入队上面同一棵树，BFS 遍历：A → B → C → D
四、核心区别对比表
| 对比项 | DFS 深度优先搜索 | BFS 广度优先搜索 |
|---|---|---|
| 核心逻辑 | 往深走，走到底再回溯 | 一层一层向外扩展 |
| 数据结构 | 栈 Stack（递归本质也是栈） | 队列 Queue |
| 内存特点 | 深度大时栈开销大；分支多内存小 | 节点多的层，队列会存大量节点；深度大内存友好 |
| 最短路径（无权图） | ❌ 不能直接得到最短路径 | ✅ 第一次访问就是最短路径 |
| 适合场景 | 找全部解、迷宫回溯、连通分量、拓扑排序 | 无权图最短路径、层级遍历、最短步数问题 |
| 时间复杂度 | O(V+E) | O(V+E) |
V 顶点数，E 边数，两者时间复杂度相同，区别主要在空间与适用场景。
五、通俗比喻
- DFS：走迷宫，碰到路口随便选一条，一直往前，撞墙就回退，试另一条路。
- BFS：洪水扩散，起点是水源，水一层一层向外漫，离起点近的地方先被淹没。
六、选型建议
求最短步数 / 最短路径（无权） → 选 BFS（例：迷宫最少步数、二叉树层序遍历）
枚举所有方案、回溯、全部路径 → 选 DFS（例：子集、全排列、找所有可行路径）
图很深，但分支少：DFS 省内存；
图很浅，但每一层节点爆炸多：BFS 会内存爆炸，改用 DFS。
注意事项：DFS 递归实现时，如果图深度非常大，会栈溢出，这时要用手动栈迭代版 DFS。
好了，今天分享到这里。希望你喜欢这次的探索之旅！不要忘记 “点赞” 和 “关注” 哦，我们下次见！🎈
本文完结！