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

DFS 和 BFS 是树、图、矩阵题的基础。面试里不会只问“DFS 是什么”，更常见的是给你一个岛屿、课程依赖、最短步数或二叉树层序遍历，让你选搜索方式并写出边界处理。一个简单判断：需要一路走到底、枚举路径或处理连通块时，优先想 DFS；需要按层推进、求最短步数时，优先想 BFS。 ## 面试考察重点 [面试考察重点](#面试考察重点) 能写递归 DFS、队列 BFS。能说出树和图搜索的复杂度。能处理 visited，避免重复访问和死循环。 ``` visited ``` 能区分“遍历所有节点”和“求最短步数”。能把矩阵题转换成图搜索。 ## 怎么选择 DFS 还是

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

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

面试考察重点

能写递归 DFS、队列 BFS。

能说出树和图搜索的复杂度。

能处理 visited，避免重复访问和死循环。

visited

能区分“遍历所有节点”和“求最短步数”。

能把矩阵题转换成图搜索。

怎么选择 DFS 还是 BFS？

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

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

目标更常用原因

目标

更常用

原因

遍历所有节点DFS 或 BFS 都可以只要不重复访问即可

遍历所有节点

DFS 或 BFS 都可以

只要不重复访问即可

找连通块面积DFS 更顺手一路递归扩展，代码短

找连通块面积

DFS 更顺手

一路递归扩展，代码短

求无权图最短步数BFS按层推进，第一次到达就是最短

求无权图最短步数

BFS

按层推进，第一次到达就是最短

枚举所有路径DFS路径天然存在递归栈里

枚举所有路径

DFS

路径天然存在递归栈里

二叉树层序遍历BFS队列正好按层处理

二叉树层序遍历

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

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。

'2'

boolean[][] visited

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

(i, j)

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

越界直接返回。

当前格子不是陆地直接返回。

标记当前格子，避免重复访问。

继续访问上下左右 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;
}

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，只处理这一层的节点；它们扩展出来的新节点属于下一层。

size

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

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

树搜索和图搜索的区别

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

visited

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

场景是否常用 visited说明

场景

是否常用 visited

visited

说明

二叉树递归遍历通常不用节点没有回到父节点的边

二叉树递归遍历

通常不用

节点没有回到父节点的边

无向图遍历需要否则两个节点会互相访问

无向图遍历

需要

否则两个节点会互相访问

有向图遍历通常需要可能存在环

有向图遍历

通常需要

可能存在环

矩阵搜索需要上下左右可能走回原点

矩阵搜索

需要

上下左右可能走回原点

复杂度

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

O(V + E)

O(V)

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

m * n

O(mn)

O(mn)

矩阵题怎么转成图？

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

常用方向数组：

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

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

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

计算新坐标。

判断是否越界。

判断是否已经访问过，或是否符合题目要求。

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

过程示意和边界样例

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

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

步骤操作目的

步骤

操作

目的

1扫描矩阵，找到一个 1发现一座新岛

扫描矩阵，找到一个 1

发现一座新岛

2岛屿数量加 1记录连通块

岛屿数量加 1

记录连通块

3从当前格子 DFS/BFS把这座岛所有陆地标记掉

从当前格子 DFS/BFS

把这座岛所有陆地标记掉

4继续扫描后续格子避免重复统计同一座岛

继续扫描后续格子

避免重复统计同一座岛

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

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

输入重点

输入

重点

空矩阵是否先判断行列长度

空矩阵

是否先判断行列长度

全是水结果应该是 0

全是水

结果应该是 0

全是陆地只能统计成 1 个连通块

全是陆地

只能统计成 1 个连通块

只有斜向相邻如果题目只允许上下左右，不能算连通

只有斜向相邻

如果题目只允许上下左右，不能算连通

常见错误写法：

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

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

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

易错点

BFS 入队时就标记访问，避免同一个节点被重复入队。

DFS 递归深度过大可能栈溢出，面试中可以说明可改成显式栈。

矩阵题先判断越界，再访问数组。

无向图要注意从子节点走回父节点的问题。

求最短步数时，BFS 的层数统计要和队列当前层大小绑定。

写在最后

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

GitHub

Gitee

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

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

知识星球