BFS vs DFS：两个模板解决所有图遍历

一句话结论（30s）

「求最短路径用 BFS、求所有路径用 DFS」——因为 BFS 按层扩散，第一次到达目标时的层数 step 天然就是最短路径长度；而 DFS 靠递归回溯能枚举出每一条路径，适合「所有排列 / 所有组合」类问题。

核心原理（2min）

• BFS 三要素：队列 + visited 集合 + 每轮 size 计数分层。size 是区分「哪些节点属于同一层」的关键——为什么会想到它？ 因为 BFS 是”先扩散、再计数”，同一批入队的节点天然属于同一层，只要在 for 循环前快照一次队列长度，就能把这一层”冻结”出来；没有它 BFS 就退化成平铺输出。
• DFS 三要素：递归 + 路径记录 + 回溯（path.add / path.remove），回溯保证回到当前状态再走别的分支。
• 取舍：BFS 占空间（需存整个队列），DFS 占栈深（深图可能栈溢出）。大图/深图优先 BFS 防递归爆栈。

底层深入（5-10min）

BFS 标准模板（队列 + visited）

void bfs(Node start) {
    Queue<Node> queue = new LinkedList<>();
    Set<Node> visited = new HashSet<>();
    queue.offer(start);
    visited.add(start);
    
    int step = 0;  // 扩散层数（最短路径长度）
    while (!queue.isEmpty()) {
        int size = queue.size();  // 本层节点数
        for (int i = 0; i < size; i++) {
            Node cur = queue.poll();
            if (isTarget(cur)) return;  // 找到目标
            for (Node next : cur.neighbors) {
                if (!visited.contains(next)) {
                    queue.offer(next);
                    visited.add(next);
                }
            }
        }
        step++;
    }
}

BFS 的核心优势：层层扩散，第一次到达目标时的 step 就是最短路径长度。为什么”第一次到达”就敢说是最短？ 因为第 step 层装的都是恰好走 step 步能到的节点，目标第一次被扫到必然落在最小的 step 层——如果还有更短路径，它早该在更小的层数被扫到了。前提是所有权重相同（如无权图），否则层数不等于距离。

💭 思考：看到什么信号该想到 BFS？——拿到题先别急着写队列，先看它问的是不是”最短”：一旦出现「最少步数 / 最短路径 / 最小操作次数」，且每一步代价相同（无权图、棋盘走一步、字符串换一个字符），就说明”层数 = 距离”，BFS 第一次扫到目标即最短。反过来，如果问的是”有几条路 / 所有走法”，BFS 只给你一条最短的，方向就错了。

DFS 标准模板（递归回溯）

void dfs(Node cur, Set<Node> visited, List<Node> path) {
    if (isTarget(cur)) {
        result.add(new ArrayList<>(path));  // 找到一条路径
        return;
    }
    for (Node next : cur.neighbors) {
        if (!visited.contains(next)) {
            visited.add(next);
            path.add(next);
            dfs(next, visited, path);       // 递归
            path.remove(path.size() - 1);  // 回溯
            visited.remove(next);
        }
    }
}

DFS 的核心优势：能枚举所有路径（配合回溯剪枝），适合”所有路径""所有排列组合”类问题。为什么回溯非要”先 add 再 remove”恢复现场？ 因为 path 是共享的一条路径，走完一个分支返回时若不清掉刚加的点，下一条分支就会被上一条分支的残留污染——恢复现场是 DFS 能”分叉”的前提。

💭 思考：看到什么信号该想到 DFS 回溯？——当题目要「枚举所有可能」（所有路径、所有排列、所有组合、所有解），本质是要把搜索空间里每一条路都走一遍，这天然是”递归 + 回溯”的形状：进一个分支前把状态加进去，走完退出来把状态擦掉。BFS 是”广度铺开”不适合存完整路径，而 DFS 的调用栈本身就记着当前这条路，所以”求全量”想到 DFS。

二叉树层序遍历

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

每层 size 计数是区分各层的关键——如果不用 size，BFS 就是平铺输出，不知道哪些节点属于同一层。

💭 思考：为什么 size 必须在 for 循环前快照一次，而不是边 poll 边取 queue.size()？——因为循环体里会把下一层的节点往队尾塞，queue.size() 是动态变化的；只有先把这个时刻的队长冻结成 size，for 循环才只处理”本层”的节点，新入队的留给下一轮。想通这一点，所有”按层”的 BFS（层序、最短路径）就都有了统一写法。

选 BFS 还是 DFS？

BFS 占空间（需存整个队列），DFS 占栈深度（可能栈溢出）。 大图选 BFS（堆 OOM 比栈溢出好排查），深图选 BFS（防递归爆栈）。

章末提问

1. 为什么 BFS 能找到最短路径，DFS 不行？ 结论：因为 BFS 按层扩散、第一次到达目标时的层数就是最短步数；DFS 是深度优先一路走到底，先到的路径未必最短，除非把每条路径都枚举完再比长度。

2. 为什么遍历要用 visited 标记，不标记会怎样？ 结论：不标记会死循环或指数级重复访问，因为图有环、节点会被反复入队/入栈；visited 让每个节点只处理一次，把复杂度从指数拉回 O(V+E)。

3. 层序遍历里去掉 size 计数还能得到正确结果吗？ 结论：能输出所有节点但不能正确分层，因为队列是先进先出的平铺序列；没有 size 就无法区分哪些节点属于同一层，结果会变成单层数组而不是二维列表。