BFS 与 DFS 模板：图、树、网格搜索的核心套路#

BFS 和 DFS 经常一起出现，但它们解决问题的侧重点并不完全一样：

DFS 更像一路走到底，适合搜索、连通块、递归遍历
BFS 更像一层一层扩散，适合最短步数、层序遍历、波纹传播

⚡ 速记版模板#

// 模板用途：BFS 按层扩展，常用于无权图最短步数与层序遍历
Queue<Integer> queue = new LinkedList<>(); // BFS 队列：先进先出，保证按层扩展
queue.offer(start); // 起点入队
visited[start] = true; // 入队即标记已访问，防止重复入队
while (!queue.isEmpty()) { // 队列非空说明还有待扩展节点
    int current = queue.poll(); // 取出当前层节点
    for (int next : graph.get(current)) { // 遍历 current 的所有邻接点
        if (!visited[next]) { // 仅处理未访问节点
            visited[next] = true; // 先标记
            queue.offer(next); // 再入队，等待后续层处理
        }
    }
}

java

🎯 什么时候想到 BFS 或 DFS？#

典型信号：

网格中的岛屿、路径、感染、扩散
树或图的遍历
连通块统计
无权图最短路径
层序遍历

Hot 100 里的典型题目：

💡 DFS 模板#

适合：

搜索所有可能路径
统计连通块
递归遍历树或图

模板一：网格 DFS#

class Solution {
    private int[][] directions = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; // 四方向数组：下、上、右、左

    private void dfs(char[][] grid, int row, int col) {
        if (row < 0 || row >= grid.length || col < 0 || col >= grid[0].length) { // 越界直接返回
            return;
        }

        if (grid[row][col] != '1') { // 不是待访问目标（如陆地）则停止扩展
            return;
        }

        grid[row][col] = '0'; // 标记已访问，避免重复 DFS

        for (int[] direction : directions) { // 递归访问四个相邻格子
            dfs(grid, row + direction[0], col + direction[1]);
        }
    }
}

java

适用：岛屿数量、连通块染色、网格遍历。

模板二：图 DFS#

class Solution {
    private List<List<Integer>> graph; // 邻接表：graph[u] 存放 u 指向的所有邻居
    private boolean[] visited; // 访问标记数组

    private void dfs(int node) {
        visited[node] = true; // 进入节点即标记，防止环导致死递归

        for (int next : graph.get(node)) { // 深度遍历所有邻居
            if (!visited[next]) { // 只递归未访问节点
                dfs(next);
            }
        }
    }
}

java

💡 BFS 模板#

适合：

最短步数
最少层数
一层一层扩散
树的层序遍历

模板三：队列式 BFS#

class Solution {
    public int bfs(int start) {
        Queue<Integer> queue = new LinkedList<>(); // BFS 队列
        boolean[] visited = new boolean[100005]; // 访问标记（这里用固定大小模板，实战按题目规模调整）
        queue.offer(start); // 起点入队
        visited[start] = true; // 入队时标记
        int steps = 0; // 记录层数（也是无权图最短步数）

        while (!queue.isEmpty()) { // 按层推进
            int size = queue.size(); // 当前层节点数
            for (int count = 0; count < size; count++) { // 处理整层节点
                int current = queue.poll(); // 当前节点

                if (isTarget(current)) { // 第一次到达目标即最短步数
                    return steps;
                }

                for (int next : getNext(current)) { // 扩展下一层候选节点
                    if (!visited[next]) {
                        visited[next] = true; // 入队前标记，避免重复
                        queue.offer(next);
                    }
                }
            }
            steps++; // 当前层处理完，步数 +1
        }

        return -1; // 无法到达目标
    }

    private boolean isTarget(int current) {
        return false; // 模板占位：判断 current 是否为目标状态
    }

    private List<Integer> getNext(int current) {
        return new ArrayList<>(); // 模板占位：生成 current 的所有下一步状态
    }
}

java

模板四：网格 BFS#

class Solution {
    int[][] directions = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; // 四方向移动向量

    public void bfs(int[][] grid, int startRow, int startCol) {
        Queue<int[]> queue = new LinkedList<>(); // 队列中存储网格坐标 [row, col]
        queue.offer(new int[]{startRow, startCol}); // 起点入队

        while (!queue.isEmpty()) { // 持续扩散
            int[] current = queue.poll(); // 取当前坐标
            int row = current[0]; // 当前行
            int col = current[1]; // 当前列

            for (int[] direction : directions) { // 遍历四邻域
                int nextRow = row + direction[0]; // 邻居行
                int nextCol = col + direction[1]; // 邻居列

                if (isValid(grid, nextRow, nextCol)) { // 判断是否可进入该格
                    markVisited(grid, nextRow, nextCol); // 先标记访问
                    queue.offer(new int[]{nextRow, nextCol}); // 再入队等待扩展
                }
            }
        }
    }

    private boolean isValid(int[][] grid, int row, int col) {
        return row >= 0 && row < grid.length && col >= 0 && col < grid[0].length; // 仅做边界检查；实战可加障碍/未访问条件
    }

    private void markVisited(int[][] grid, int row, int col) {
        // 模板占位：将该格标记为已访问（如改值、写 visited 数组）
    }
}

java

🧠 BFS 和 DFS 怎么选？#

求最短路径 / 最少步数：优先 BFS
只要遍历 / 搜索所有方案：常用 DFS
树的层序遍历：BFS
回溯搜索路径：DFS
拓扑排序：通常 BFS 或 DFS 都能做

⚠️ 易错点#

访问标记时机错误
- BFS 通常在入队时标记
- 否则可能重复入队
DFS 忘记终止条件
- 特别是网格问题，越界和已访问判断要放前面
BFS 层数统计错位
- 要先取当前层 size
- 再处理这一整层
图问题忘记建邻接表
- 特别是课程表这类题，先建图再遍历

🎨 面试时怎么说#

你可以这样说：

如果题目要的是最少步数，我会优先 BFS，因为它天然按层扩展，第一次到达目标就是最短路径；如果题目要的是遍历或搜索所有可能，我会优先 DFS。

📌 一句话总结#

BFS：层层扩散，适合最短路和层序问题
DFS：深入搜索，适合遍历、连通块和递归问题