第10章广度优先搜索（BFS）

课程目录第10章广度优先搜索（BFS）

第10章：广度优先搜索（BFS）——层层推进的搜索艺术

说实话，BFS 是我个人非常喜欢的一种算法。为什么？因为它特别「稳」。你想想看，它不像 DFS 那样一条路走到黑，而是一层一层地往外扩散，像水波一样。我在项目中处理过不少图相关的问题，BFS 的出镜率真的很高。

10.1 BFS 的核心思想

BFS，全称 Breadth-First Search，中文叫广度优先搜索。它的核心逻辑就一句话：从起点出发，先访问所有距离为 1 的节点，再访问所有距离为 2 的节点，以此类推。

说白了，就是「先来后到」——谁离我近，我先处理谁。

核心数据结构：队列（Queue）

BFS 必须用队列。为什么？因为队列是先进先出（FIFO）的，正好符合「先访问到的节点先扩展」的需求。你要是用栈，那就变成 DFS 了。

10.2 BFS 的通用模板

我写 BFS 这么多年，总结下来就一个模板。你把这个背下来，90% 的 BFS 题都能套。

// BFS 通用模板（Java 版）
public void bfs(Node start) {
    if (start == null) return;
    
    Queue<Node> queue = new LinkedList<>();
    Set<Node> visited = new HashSet<>();  // 防止走回头路
    
    queue.offer(start);
    visited.add(start);
    
    while (!queue.isEmpty()) {
        int size = queue.size();  // 当前层的节点数
        
        // 遍历当前层的所有节点
        for (int i = 0; i < size; i++) {
            Node cur = queue.poll();
            
            // 处理当前节点
            process(cur);
            
            // 把相邻的未访问节点加入队列
            for (Node neighbor : cur.neighbors) {
                if (!visited.contains(neighbor)) {
                    queue.offer(neighbor);
                    visited.add(neighbor);
                }
            }
        }
        
        // 这里可以记录层数，比如 step++
    }
}

我的小习惯：我一般会在 while 循环里用 int size = queue.size() 来分层。这样既能知道当前在第几层，又能方便地处理「最短路径」问题。

10.3 为什么 BFS 适合求最短路径？

这个问题我经常被问到。其实原因很简单：BFS 是按层遍历的，第一次到达目标节点时，走的路径一定是最短的。

你想想看，如果从起点到终点有两条路，一条长一条短。BFS 会先走完所有长度为 1 的路径，再走长度为 2 的……所以当它第一次碰到终点时，那一定是最短的那条。

DFS 就不行。DFS 可能先走了一条很长的路才找到终点，这时候你没法确定是不是最短的。

注意：BFS 求最短路径的前提是「所有边的权重相同」。如果边的权重不同，那就得用 Dijkstra 算法了。我曾经在项目中踩过这个坑，图里边的权重不一样，我直接用 BFS 去求最短路径，结果算出来是错的……嗯，从那以后我就记住了这个前提。

10.4 经典例题一：二叉树层序遍历

这是 BFS 最经典的入门题。给你一棵二叉树，按层输出每个节点的值。

// 二叉树层序遍历
public List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> result = new ArrayList<>();
    if (root == null) return result;
    
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    
    while (!queue.isEmpty()) {
        int size = queue.size();
        List<Integer> level = new ArrayList<>();
        
        for (int i = 0; i < size; i++) {
            TreeNode node = queue.poll();
            level.add(node.val);
            
            if (node.left != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
        }
        
        result.add(level);
    }
    
    return result;
}

你看，这个代码跟模板几乎一模一样。唯一的区别就是处理节点的逻辑变成了「把值加入当前层的列表」。

10.5 经典例题二：单词接龙

这道题稍微有点难度，但核心还是 BFS。题目是这样的：给你一个开始单词、一个结束单词和一个单词列表，每次只能改变一个字母，问从开始单词到结束单词的最短转换序列长度。

我当年第一次做这道题时，想的是用 DFS 暴力搜索，结果超时了。后来换成 BFS，一下就过了。为什么？因为 BFS 找到的第一个解就是最短的，不用遍历所有可能。

// 单词接龙 - BFS 解法
public int ladderLength(String beginWord, String endWord, List<String> wordList) {
    Set<String> wordSet = new HashSet<>(wordList);
    if (!wordSet.contains(endWord)) return 0;
    
    Queue<String> queue = new LinkedList<>();
    Set<String> visited = new HashSet<>();
    
    queue.offer(beginWord);
    visited.add(beginWord);
    
    int step = 1;  // 包含起始单词
    
    while (!queue.isEmpty()) {
        int size = queue.size();
        
        for (int i = 0; i < size; i++) {
            String cur = queue.poll();
            
            // 尝试改变每个位置的字母
            char[] chars = cur.toCharArray();
            for (int j = 0; j < chars.length; j++) {
                char original = chars[j];
                
                for (char c = 'a'; c <= 'z'; c++) {
                    if (c == original) continue;
                    
                    chars[j] = c;
                    String next = new String(chars);
                    
                    if (next.equals(endWord)) {
                        return step + 1;
                    }
                    
                    if (wordSet.contains(next) && !visited.contains(next)) {
                        queue.offer(next);
                        visited.add(next);
                    }
                }
                
                chars[j] = original;  // 恢复
            }
        }
        
        step++;
    }
    
    return 0;  // 没找到
}

优化小技巧：如果单词列表很大，可以考虑用「双向 BFS」。从起点和终点同时开始搜索，当两个搜索相遇时，路径就是最短的。我在处理超长单词列表时经常用这个技巧，速度能快好几倍。

10.6 BFS 的变种与扩展

变种	适用场景	核心区别
标准 BFS	无权图最短路径	按层遍历，队列实现
双向 BFS	起点和终点已知	两端同时搜索，减少搜索空间
优先队列 BFS	带权图（Dijkstra）	用优先队列代替普通队列
多源 BFS	多个起点同时扩散	初始化时把所有起点加入队列

10.7 BFS 的知识体系

下面这张图是我整理的 BFS 知识体系，你可以把它当作复习地图。

10.8 避坑指南

最后，分享几个我踩过的坑：

忘记标记 visited：我曾经在写 BFS 时忘了标记已访问节点，结果队列里无限循环，程序直接 OOM。嗯，从那以后我写 BFS 的第一件事就是初始化 visited 集合。
在循环内修改队列大小：如果你在遍历当前层时往队列里加元素，一定要先保存当前层的 size。否则你会把下一层的节点也当成当前层的来处理。
忽略起点等于终点的情况：有些题目起点就是终点，这时候直接返回 0 或 1。我见过不少人在这个边界条件上翻车。

好了，BFS 的内容就讲到这里。记住那个模板，多刷几道题，你就能掌握它了。

公众号:蓝海资料掘金营，微信deep3321

📚 课程目录