dfs-bfs.md

title	DFS 与 BFS 面试题总结：树、图、矩阵搜索与最短路径模板
description	DFS 与 BFS 面试题总结，讲解深度优先搜索、广度优先搜索、树遍历、图遍历、矩阵搜索、层序遍历、最短路径和 Java 模板。
category	计算机基础
tag	算法
head	meta name content keywords DFS,BFS,深度优先搜索,广度优先搜索,树遍历,图遍历,矩阵搜索,层序遍历,最短路径,Java DFS,Java BFS,LeetCode

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 的层数统计要和队列当前层大小绑定。

推荐练习题

• 102. 二叉树的层序遍历
• 200. 岛屿数量
• 695. 岛屿的最大面积
• 994. 腐烂的橘子
• 207. 课程表