跳至主要內容

DFS 与 BFS 面试题总结：树、图、矩阵搜索与最短路径模板

Guide计算机基础算法约 1849 字大约 6 分钟

DFS 和 BFS 是树、图、矩阵题的基础。面试里不会只问“DFS 是什么”，更常见的是给你一个岛屿、课程依赖、最短步数或二叉树层序遍历，让你选搜索方式并写出边界处理。

一个简单判断：需要一路走到底、枚举路径或处理连通块时，优先想 DFS；需要按层推进、求最短步数时，优先想 BFS。

面试考察重点

  • 能写递归 DFS、队列 BFS。
  • 能说出树和图搜索的复杂度。
  • 能处理 visited，避免重复访问和死循环。
  • 能区分“遍历所有节点”和“求最短步数”。
  • 能把矩阵题转换成图搜索。

怎么选择 DFS 还是 BFS？

DFS 和 BFS 都能遍历节点，但它们的天然优势不同。

目标更常用原因
遍历所有节点DFS 或 BFS 都可以只要不重复访问即可
找连通块面积DFS 更顺手一路递归扩展，代码短
求无权图最短步数BFS按层推进，第一次到达就是最短
枚举所有路径DFS路径天然存在递归栈里
二叉树层序遍历BFS队列正好按层处理

如果题目里出现“最少几步”“最短路径”“扩散到所有位置”，先想 BFS。如果题目里出现“所有方案”“是否存在一条路径”“连通块大小”，先想 DFS。

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);
}

这里直接把访问过的陆地改成 '2'，相当于使用原数组做访问标记。如果题目不允许修改输入，就单独建 boolean[][] visited。

DFS 的递归函数要先定义清楚含义。上面这段代码可以解释为：从 (i, j) 出发，把和它连通的所有陆地都标记掉。

这个含义决定了代码顺序：

  1. 越界直接返回。
  2. 当前格子不是陆地直接返回。
  3. 标记当前格子，避免重复访问。
  4. 继续访问上下左右 4 个方向。

很多 DFS bug 都来自第 3 步写晚了。如果先递归邻居，再标记当前节点，就可能在两个相邻格子之间来回递归。

BFS 模板

BFS 适合层序遍历和最短步数：

int bfs(int[][] grid, int startX, int startY) {
    int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    Queue<int[]> queue = new ArrayDeque<>();
    queue.offer(new int[] {startX, startY});
    boolean[][] visited = new boolean[grid.length][grid[0].length];
    visited[startX][startY] = true;
    int step = 0;
    while (!queue.isEmpty()) {
        int size = queue.size();
        for (int k = 0; k < size; k++) {
            int[] cur = queue.poll();
            for (int[] dir : dirs) {
                int x = cur[0] + dir[0];
                int y = cur[1] + dir[1];
                if (x < 0 || x >= grid.length || y < 0 || y >= grid[0].length || visited[x][y]) {
                    continue;
                }
                visited[x][y] = true;
                queue.offer(new int[] {x, y});
            }
        }
        step++;
    }
    return step;
}

如果题目要求最短路径，通常在发现目标节点时返回当前步数，而不是等队列清空。

BFS 的关键是“按层处理”。队列里一开始是第 0 层节点，每轮取出当前队列大小 size，只处理这一层的节点；它们扩展出来的新节点属于下一层。

为什么无权图 BFS 能求最短路径？因为每条边的代价相同。BFS 第一次到达某个节点时，一定是用了最少的边数。后面即使还能再次到达，也不会更短，所以可以直接标记访问。

多源 BFS 也很常见。比如“腐烂的橘子”里，所有烂橘子同时开始扩散。做法是先把所有初始烂橘子都入队，再按层扩散。

树搜索和图搜索的区别

树没有环，很多时候不需要 visited。图可能有环，必须考虑重复访问。

场景是否常用 visited说明
二叉树递归遍历通常不用节点没有回到父节点的边
无向图遍历需要否则两个节点会互相访问
有向图遍历通常需要可能存在环
矩阵搜索需要上下左右可能走回原点

复杂度

图搜索常用 V 表示顶点数，E 表示边数。邻接表存储时，DFS 和 BFS 的时间复杂度通常是 O(V + E)，空间复杂度是 O(V)。

矩阵搜索如果矩阵大小是 m * n，每个格子最多访问一次，时间复杂度是 O(mn)，访问标记或队列空间最坏也是 O(mn)。

矩阵题怎么转成图？

矩阵中的每个格子都可以看成图里的一个节点。上下左右 4 个方向，就是这个节点连出去的边。

常用方向数组：

int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

遍历邻居时只需要做 3 件事：

  1. 计算新坐标。
  2. 判断是否越界。
  3. 判断是否已经访问过，或是否符合题目要求。

如果题目允许斜向移动，把方向数组扩展成 8 个方向即可。不要在代码里手写 4 段几乎相同的递归调用，方向数组更不容易漏条件。

过程示意和边界样例

以岛屿数量为例，遇到一个未访问过的陆地格子，就从它开始 DFS/BFS，把整座岛都标记掉。

步骤操作目的
1扫描矩阵，找到一个 1发现一座新岛
2岛屿数量加 1记录连通块
3从当前格子 DFS/BFS把这座岛所有陆地标记掉
4继续扫描后续格子避免重复统计同一座岛

矩阵搜索建议检查这些边界：

输入重点
空矩阵是否先判断行列长度
全是水结果应该是 0
全是陆地只能统计成 1 个连通块
只有斜向相邻如果题目只允许上下左右，不能算连通

常见错误写法：

void dfs(char[][] grid, int i, int j) {
    dfs(grid, i + 1, j);
    grid[i][j] = '2'; // 错：标记太晚，可能来回递归
}

访问标记要在递归扩展邻居之前完成。图和矩阵里只要存在回边或相邻互访，标记太晚就可能重复访问甚至栈溢出。

易错点

  • BFS 入队时就标记访问，避免同一个节点被重复入队。
  • DFS 递归深度过大可能栈溢出，面试中可以说明可改成显式栈。
  • 矩阵题先判断越界，再访问数组。
  • 无向图要注意从子节点走回父节点的问题。
  • 求最短步数时，BFS 的层数统计要和队列当前层大小绑定。

推荐练习题

写在最后

如果内容对你有帮助的话，欢迎顺手给 JavaGuide 点一个免费的 Star 支持一下：GitHub | Gitee。

JavaGuide 已持续维护近七年，累计 6100+ 次提交，来自 620+ 位贡献者共同完善。你的 Star、反馈和 PR，都是这个项目继续更新的动力。

如果你正在准备后端/AI 应用开发面试，也可以了解一下我的知识星球，里面包括后端和 AI 实战项目、简历优化、一对一提问和高频考点资料，已经持续维护六年。

编辑此页
最近更新:
贡献者: Guide,Mr.Hope