BFS 解决边权相同最短路问题的四个实战案例

时间复杂度：O(MN)，空间复杂度：O(MN)

2. 最小基因变化

问题场景：起始字符串 startGene 变为 endGene，每次只能变一个字符，且变化后的字符串必须在基因库 bank 中。求最少变化次数。

核心思路：这其实是一个隐式图的最短路径问题。每个基因串是节点，单次合法突变是边。由于边权相同，直接用 BFS。关键点在于如何高效判断突变是否合法，这里用 HashSet 存储基因库和已访问状态。

参考实现：

import java.util.*;

class Solution {
    public int minMutation(String startGene, String endGene, String[] bank) {
        Set<String> flag = new HashSet<>(); // 标记改变过的基因
        Set<String> hash = new HashSet<>(); // 记录基因库 bank 元素
        for (String s : bank) hash.add(s);

        // end 基因无效
        if (!hash.contains(endGene)) return -1;

        Queue<String> queue = new LinkedList<>();
        queue.add(startGene);
        flag.add(startGene);
        int length = 0;
        char[] change = {'A', 'C', 'G', 'T'};

        while (!queue.isEmpty()) {
            int size = queue.size();
            length++; // 层序遍历，相当于突变一次
            for (int i = 0; i < size; i++) {
                String t = queue.poll();
                // 遍历字符串的字符，一一突变
                for (int j = 0; j < 8; j++) {
                    char[] tmp = t.toCharArray();
                    // 尝试四种碱基
                    for (int k = 0; k < 4; k++) {
                        tmp[j] = change[k];
                        String next = new String(tmp);
                        // 入队条件：在基因库且未访问过
                        if (hash.contains(next) && !flag.contains(next)) {
                            queue.add(next);
                            flag.add(next);
                        }
                        // 结束条件
                        if (next.equals(endGene)) return length;
                    }
                }
            }
        }
        return -1;
    }
}

时间复杂度：O(N)，空间复杂度：O(N)

3. 单词接龙

问题场景：与上一题类似，只是突变规则变成了 26 个小写字母，且字典为 wordList。

核心思路：逻辑完全一致，区别在于字符集扩大到了 26 个字母。同样需要利用 HashSet 快速查找是否存在该单词，并记录已访问状态防止死循环。

参考实现：

import java.util.*;

class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        Set<String> hash = new HashSet<>();
        for (String s : wordList) hash.add(s);

        // endWord 不在字典
        if (!hash.contains(endWord)) return 0;

        // 标记表
        Set<String> flag = new HashSet<>();
        flag.add(beginWord);
        Queue<String> queue = new LinkedList<>();
        queue.add(beginWord);
        int ret = 1;

        while (!queue.isEmpty()) {
            int size = queue.size();
            ret++;
            for (int k = 0; k < size; k++) {
                String s = queue.poll();
                for (int i = 0; i < s.length(); i++) {
                    char[] tmp = s.toCharArray();
                    // 26 个字母尝试替换
                    for (char j = 'a'; j <= 'z'; j++) {
                        tmp[i] = j;
                        String string = new String(tmp);
                        // 入队条件
                        if (hash.contains(string) && !flag.contains(string)) {
                            queue.add(string);
                            flag.add(string);
                        }
                        // 结束条件
                        if (string.equals(endWord)) return ret;
                    }
                }
            }
        }
        return 0;
    }
}

时间复杂度：O(N)，空间复杂度：O(N)

4. 为高尔夫比赛砍树

问题场景：给定二维矩阵，按树的高度从小到大依次砍树。计算从当前位置到下一棵树的总最短路径。

核心思路：这是一个多阶段 BFS 问题。首先提取所有树的位置并按高度排序。然后从起点开始，依次对每一对相邻的树运行 BFS 计算最短距离。注意如果某棵树位置是地面（值为 1），则跳过；如果中间无法到达某棵树，直接返回 -1。

参考实现：

import java.util.*;

class Solution {
    int[] dx = {1, -1, 0, 0};
    int[] dy = {0, 0, 1, -1};
    int m, n;

    public int cutOffTree(List<List<Integer>> forest) {
        m = forest.size();
        n = forest.get(0).size();

        // 找出砍树的顺序，根据树的大小排序
        List<int[]> trees = new ArrayList<>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (forest.get(i).get(j) > 0) trees.add(new int[]{i, j});
            }
        }
        Collections.sort(trees, (a, b) -> {
            return forest.get(a[0]).get(a[1]) - forest.get(b[0]).get(b[1]);
        });

        int ret = 0;
        int beginX = 0;
        int beginY = 0;

        for (int[] tree : trees) {
            int endX = tree[0];
            int endY = tree[1];
            int tep = 0;

            // 下一步是地面，跳过
            if (forest.get(endX).get(endY) == 1) continue;

            tep = bfs(forest, beginX, beginY, endX, endY);
            if (tep == -1) return -1;
            ret += tep;
            beginX = endX;
            beginY = endY;
        }
        return ret;
    }

    // ab 代表下一棵砍的坐标，xy 表示当前的位置
    public int bfs(List<List<Integer>> forest, int beginX, int beginY, int endX, int endY) {
        // 当前就是要砍的树
        if ((beginX == endX && beginY == endY)) return 0;

        // 标记数组，走过的路
        boolean[][] flag = new boolean[m][n];
        int tep = 0;
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{beginX, beginY});
        flag[beginX][beginY] = true;

        while (!queue.isEmpty()) {
            int size = queue.size();
            tep++;
            while (size-- != 0) {
                int[] arr = queue.poll();
                int nx, ny;
                for (int i = 0; i < 4; i++) {
                    nx = arr[0] + dx[i];
                    ny = arr[1] + dy[i];
                    // 入队条件
                    if (nx >= 0 && nx < m && ny >= 0 && ny < n 
                        && !flag[nx][ny] && forest.get(nx).get(ny) != 0) {
                        queue.add(new int[]{nx, ny});
                        flag[nx][ny] = true;
                        // 到了
                        if (nx == endX && ny == endY) return tep;
                    }
                }
            }
        }
        return -1;
    }
}

时间复杂度：O(N)，空间复杂度：O(N)