广度优先搜索 vs 深度优先搜索
图的两种基本遍历策略：BFS按层扩展探索最近顶点，DFS沿深度优先探索最远顶点
共同点
- 时间复杂度均为 O(V+E)
- 都需要访问标记（颜色数组）避免重复访问
- 都构建前驱子图（π数组）形成生成树/森林
- 都是许多高级图算法的基础构件
关键区别
| 维度 | 广度优先搜索 | 深度优先搜索 |
|---|---|---|
| 数据结构 | FIFO 队列 | 栈（递归调用栈或显式栈） |
| 探索策略 | 层序扩展（先近后远） | 深度优先（先远后回溯） |
| 发现顺序 | 按距源点的距离递增 | 按DFS树的先序遍历 |
| 最短路径 | 保证无权图最短路径 | 不保证最短路径 |
| 空间复杂度 | O(V)（队列） | O(V)（递归栈最坏情况） |
| 边分类 | 树边/非树边（不细分） | 树边/回边/前向边/横叉边 |
| 时间戳 | 无 | d[u]/f[u] 发现/完成时间 |
| 适用场景 | 最短路径、层次遍历 | 拓扑排序、SCC、环检测 |
| 不变量 | BFS层次性质 | 括号定理、白色路径定理 |
深层联系
- 对偶性：BFS使用队列（FIFO），DFS使用栈（LIFO），两者是数据结构对偶在图遍历中的体现
- 统一框架：两者都可以看作通用图搜索（Generic Search）的特例，区别仅在于边缘集合（fringe）的存储结构
- 互补应用：Kosaraju算法同时使用两种遍历——第一次DFS计算完成时间，第二次BFS（在转置图上）发现SCC