DFS 与 BFS 是遍历状态空间的两种范式：一个借助栈一条路走到底再回退，一个借助队列按距离逐层扩散。二者的差别不在代码长短，而在”待处理节点按什么顺序取出”——正是这个顺序，决定了 DFS 擅长枚举与连通性，BFS 垄断无权图最短路。

它解决什么问题

树、图、矩阵、棋盘都可以抽象成状态图：节点是状态，边是状态间的转移。DFS 与 BFS 解决的是”如何不重不漏地访问所有可达状态”，并在此之上衍生出连通块统计、路径枚举、层级展开、最短步数等具体问题。面试很少让你背定义，而是给一座岛屿、一张课程表或一个迷宫，考察你能否把题目翻译成状态图，并选对遍历顺序。

核心原理

两种遍历共享同一个骨架：从起点出发，把邻居放入”待处理容器”，逐个取出并扩展新邻居。唯一区别是容器——DFS 用栈，后发现的邻居先处理，于是不断深入；BFS 用队列，先发现的先处理，于是同一层的节点一起扩展。DFS 的栈可以直接复用递归调用栈，代码极短；BFS 必须显式维护队列，而”层”的信息天然保存在队列长度的快照里。

访问标记是两条范式的共同生命线：图有环、矩阵相邻互通，不标记就会死循环。经验法则是入容器时就标记，而不是取出时才标记，否则同一节点会被多个前驱重复塞入。树从根到叶天然无环，多数情况下可以省掉 visited。

深入机制

BFS：层序遍历与无权最短路

二叉树层序遍历是 BFS 最干净的形态：每轮循环先固定队列当前长度 size，只处理这 size 个节点，它们扩展出的孩子属于下一层：

List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> res = new ArrayList<>();
    if (root == null) return res;
    Queue<TreeNode> q = new ArrayDeque<>();
    q.offer(root);
    while (!q.isEmpty()) {
        int size = q.size();              // 当前层节点数快照
        List<Integer> level = new ArrayList<>();
        for (int i = 0; i < size; i++) {
            TreeNode cur = q.poll();
            level.add(cur.val);
            if (cur.left != null) q.offer(cur.left);
            if (cur.right != null) q.offer(cur.right);
        }
        res.add(level);
    }
    return res;
}

同一个骨架平移到图上，就是无权图最短路：每条边代价相同，BFS 第 d 层恰好收纳”距起点 d 步”的所有节点，目标第一次出队时的层数就是最少步数。这个性质只对无权（或边权全相等）图成立——边权不同但非负时应换 Dijkstra，有负权边则连 Dijkstra 都失效。多源最短路（如腐烂橘子扩散）只需把所有源点开局一起入队，等价于虚拟出一个超级源点。

DFS：连通块与回溯剪枝

岛屿数量是 DFS 统计连通块的模板题：扫描矩阵，每发现一块未访问的陆地就计数加一，并立刻从它出发把整座岛”淹掉”，保证后续不会重复计数：

void dfs(char[][] grid, int i, int j) {
    if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length) return;
    if (grid[i][j] != '1') return;        // 水或已访问，直接剪枝
    grid[i][j] = '2';                     // 先标记，再扩展邻居
    dfs(grid, i + 1, j); dfs(grid, i - 1, j);
    dfs(grid, i, j + 1); dfs(grid, i, j - 1);
}

标记必须发生在递归扩展邻居之前——写反了会在相邻格子间来回递归直至栈溢出；题目不允许改输入时就换成 boolean[][] visited。

当 DFS 用来枚举所有解（全排列、子集、N 皇后）时，就进入了回溯模式：递归栈天然保存当前路径，试探一步、递归、再撤销这一步。剪枝是回溯的灵魂——在进入分支前用约束条件把注定失败的子树整棵砍掉：排列题用 used 数组跳过已选元素，棋盘题落子前检查行列与对角冲突。剪枝不改变复杂度上界，但能把实际搜索量压掉几个数量级。

复杂度上，邻接表存图时 DFS 与 BFS 都是 O(V+E) 时间、O(V) 空间；m×n 矩阵搜索是 O(mn)。递归 DFS 的隐形成本是调用栈深度：链式树或深图上可能栈溢出，工程实现要改显式栈。

工程实践

  • 方向数组代替四段复制：int[][] dirs = {{1,0},{-1,0},{0,1},{0,-1}}，循环展开邻居，越界判断只写一处；改八连通只需再加四个方向。
  • 判环与拓扑：DFS 三色标记（未访问 / 递归栈中 / 已完成）可判有向图的环并输出拓扑序；课程表类问题两条路都通——DFS 判环，或 BFS 配合入度削点（Kahn 算法）。
  • 容器选型：Java 里用 ArrayDeque 当队列和栈，数组实现缓存更友好；避免 LinkedList 当队列、避免遗留的 Stack 类。

对比与权衡

维度 DFS BFS
容器 栈 / 递归调用栈 显式队列
扩展顺序 深者先至 近者先至
空间占用 最深路径 O(h) 最宽一层 O(w)，可能远大于 h
无权图最短步数 不能保证 首次到达即最短
典型用途 连通块、路径枚举、回溯、拓扑 层序遍历、无权最短路、多源扩散
主要风险 深递归栈溢出 宽图队列吃内存

判断口诀：要”走到底、枚举全部、数连通块”用 DFS；要”按层来、最少几步、最近距离”用 BFS。树深而窄时 DFS 省空间；图浅而宽时 BFS 的队列可能比 DFS 的栈更吃内存，空间开销要按实际形态评估。

面试视角

为什么 BFS 能求无权图最短路？ 边权相同时 BFS 按步数从小到大逐层扩展，节点第一次被访问走的就是边数最少的路径，之后再到不可能更短，因此入队时即可放心标记。

DFS 的标记时机为什么必须在递归之前？ 相邻节点互为邻居，若先递归再标记，A 扩展 B、B 回头又扩展未标记的 A，形成无限递归。先标记再扩展才能保证每个节点只进入一次。

岛屿数量能用 BFS 吗？ 可以，等价替换：发现陆地后入队扩散、标记整岛，计数逻辑不变。DFS 代码更短，BFS 在大矩阵下不怕栈溢出，按数据规模取舍。

回溯和普通 DFS 的区别是什么？ 回溯是带撤销的 DFS：进入分支时做选择，返回前撤销，配合剪枝枚举全部解。回溯的标记是”路径级”的、出递归要还原；连通性问题的标记是全局的、不撤销。

什么时候 DFS 与 BFS 都不够？ 非负带权最短路交给 Dijkstra；状态空间巨大且要求最优解时，用回溯加剪枝、动态规划，或双向 BFS、A* 等带启发式的搜索。

小结

  • DFS 与 BFS 只差一个容器：栈让深者先至，队列让近者先至，这个顺序决定了两者的能力边界。
  • 标记在入容器时完成；回溯的标记随路径撤销，连通性的标记全局保留。
  • BFS 求最短路的唯一前提是所有边等权，否则交给 Dijkstra。
  • 把题目翻译成”状态 + 转移”的图之后，遍历方式的选择往往就自动浮现了。