双向广搜算法详解

常规广度优先搜索（BFS）中，当搜索空间较大时，算法可能需要遍历大量节点才能找到目标，效率较低，双向广搜（Bidirectional BFS）作为BFS的优化算法，通过从起点和终点同时开始搜索，在中间相遇时终止，能显著减少搜索的节点数量，大幅提升搜索效率。

一、双向广搜基础概念

1.1 算法核心思想

双向广搜算法的核心是“从两个方向同时搜索，在中间相遇时停止”。具体来说：

• 从起点（正向搜索）和终点（反向搜索）分别启动BFS。
• 每次搜索时，选择当前规模较小的搜索队列进行扩展（平衡两个方向的搜索进度）。
• 当两个搜索方向在某个节点相遇（即该节点同时出现在两个搜索的已访问集合中），则找到一条从起点到终点的最短路径。
  

这种方式避免了传统BFS从单方向盲目扩展到远距离目标的问题，能有效减少搜索的节点总数（搜索规模从O(2^d)降至O(2^(d/2))，d为最短路径长度）。

1.2 适用场景

双向广搜适用于以下场景：

• 最短路径问题：如迷宫寻路、单词接龙、数字变换等需要找到最短路径的场景。
• 状态空间较大：当单方向BFS需要遍历大量节点时，双向广搜的优势更明显。
• 起点和终点明确：算法需要同时知道起点和终点，才能从两个方向启动搜索。

1.3 与传统BFS的对比

二、双向广搜的实现步骤

2.1 初始化

• 定义两个队列：正向队列（存储从起点扩展的节点）和反向队列（存储从终点扩展的节点）。
• 定义两个已访问集合：正向访问集（记录正向搜索已遍历的节点）和反向访问集（记录反向搜索已遍历的节点）。
• 将起点加入正向队列和正向访问集，将终点加入反向队列和反向访问集。
• 初始化搜索步数（正向步数和反向步数）。

2.2 双向搜索循环

• 若正向队列或反向队列为空，说明不存在路径，算法结束。
• 选择当前规模较小的队列（平衡搜索进度），对其进行一层扩展：
  • 遍历队列中当前所有节点（按层扩展，保证步数准确）。
  • 对每个节点的邻接节点（下一步可能的状态）进行判断：
    • 若邻接节点在对方的访问集中（如正向扩展的节点出现在反向访问集中），则找到路径，返回总步数（正向步数+反向步数+1）。
    • 若邻接节点未在当前方向的访问集中，将其加入队列和访问集。
• 增加对应方向的搜索步数，重复循环。

2.3 路径还原（可选）

若需要具体路径而非仅步数，可在访问集中记录每个节点的前驱（正向）或后继（反向），相遇后从相遇节点向前回溯至起点，向后回溯至终点，拼接得到完整路径。

三、Java代码实现（以单词接龙为例）

以下是基于双向广搜解决“单词接龙”问题的实现。问题描述：给定两个单词（beginWord和endWord）和一个单词列表，找到从beginWord到endWord的最短转换序列（每次转换只能改变一个字母，且转换后的单词必须在列表中）。

import java.util.*;

public class BidirectionalBFS {
    // 单词接龙：双向广搜实现
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        Set<String> wordSet = new HashSet<>(wordList);
        // 若终点不在单词列表中，直接返回0
        if (!wordSet.contains(endWord)) {
            return 0;
        }

        // 初始化正向和反向搜索
        Queue<String> forwardQueue = new LinkedList<>();
        Queue<String> backwardQueue = new LinkedList<>();
        Set<String> forwardVisited = new HashSet<>();
        Set<String> backwardVisited = new HashSet<>();

        forwardQueue.add(beginWord);
        forwardVisited.add(beginWord);
        backwardQueue.add(endWord);
        backwardVisited.add(endWord);

        int steps = 1; // 初始步数（起点和终点各算1步）

        // 双向BFS循环
        while (!forwardQueue.isEmpty() && !backwardQueue.isEmpty()) {
            // 选择规模较小的队列扩展，平衡搜索
            if (forwardQueue.size() > backwardQueue.size()) {
                // 交换队列和访问集，统一处理逻辑
                Queue<String> tempQueue = forwardQueue;
                forwardQueue = backwardQueue;
                backwardQueue = tempQueue;

                Set<String> tempVisited = forwardVisited;
                forwardVisited = backwardVisited;
                backwardVisited = tempVisited;
            }

            // 扩展当前层（正向队列）
            int size = forwardQueue.size();
            for (int i = 0; i < size; i++) {
                String current = forwardQueue.poll();
                // 生成所有可能的下一个单词
                List<String> neighbors = getNeighbors(current, wordSet);

                for (String neighbor : neighbors) {
                    // 若在反向访问集中找到，说明相遇
                    if (backwardVisited.contains(neighbor)) {
                        return steps + 1;
                    }
                    // 若未访问过，加入队列和访问集
                    if (!forwardVisited.contains(neighbor)) {
                        forwardVisited.add(neighbor);
                        forwardQueue.add(neighbor);
                    }
                }
            }

            steps++;
        }

        // 未找到路径
        return 0;
    }

    // 生成当前单词的所有可能邻接单词（改变一个字母且在单词集中）
    private List<String> getNeighbors(String word, Set<String> wordSet) {
        List<String> neighbors = new ArrayList<>();
        char[] chars = word.toCharArray();
        // 遍历每个字符位置
        for (int i = 0; i < chars.length; i++) {
            char original = chars[i];
            // 尝试替换为a-z中其他字符
            for (char c = 'a'; c <= 'z'; c++) {
                if (c == original) {
                    continue;
                }
                chars[i] = c;
                String newWord = new String(chars);
                if (wordSet.contains(newWord)) {
                    neighbors.add(newWord);
                }
            }
            chars[i] = original; // 恢复原字符
        }
        return neighbors;
    }

    // 测试
    public static void main(String[] args) {
        BidirectionalBFS solver = new BidirectionalBFS();
        String beginWord = "hit";
        String endWord = "cog";
        List<String> wordList = Arrays.asList("hot", "dot", "dog", "lot", "log", "cog");

        int result = solver.ladderLength(beginWord, endWord, wordList);
        System.out.println("最短转换序列长度：" + result); // 输出5（hit->hot->dot->dog->cog）
    }
}

代码说明

• 核心逻辑：通过正向和反向两个队列分别从起点和终点搜索，每次扩展规模较小的队列，相遇时返回总步数。
• 邻接生成：getNeighbors方法生成当前单词的所有可能变体（改变一个字母），并过滤出在单词集中的有效变体。
• 平衡策略：通过交换队列保证每次扩展规模较小的方向，避免一个方向搜索过快导致的效率下降。

四、双向广搜的优化技巧

4.1 平衡两个方向的搜索进度

• 选择小规模队列扩展：每次迭代时，优先扩展当前元素数量较少的队列（如正向队列有3个节点，反向队列有5个节点，则先扩展正向队列）。这种方式能避免一个方向过度扩展，平衡两个方向的搜索范围。
• 限制单次扩展层数：每次对队列进行“一层扩展”（即遍历当前队列中的所有节点，生成下一层节点），保证两个方向的搜索按“步数”同步推进。

4.2 高效的邻接节点生成

邻接节点的生成效率直接影响算法性能。在单词接龙等问题中，可通过以下方式优化：

• 预处理单词：将单词按“模式”分组（如“hot”可归为“ot”“ht”“ho*”），生成邻接单词时直接查询同模式的单词，避免逐个字符替换的冗余计算。
• 剪枝无效节点：生成邻接节点时，直接过滤不在目标集合（如单词列表）中的节点，减少无效扩展。

4.3 路径还原的实现

若需要获取具体路径而非仅步数，可在访问集中存储“前驱”或“后继”关系：

• 正向访问集存储节点->前驱节点（记录从起点到该节点的路径）。
• 反向访问集存储节点->后继节点（记录从该节点到终点的路径）。
• 相遇时，从相遇节点向前回溯至起点，向后回溯至终点，拼接得到完整路径。

五、应用场景

5.1 迷宫寻路

在二维迷宫中，从起点到终点的最短路径可通过双向广搜实现。正向搜索从起点扩展，反向搜索从终点扩展，相遇时得到最短路径，比传统BFS减少大量无效探索。

5.2 数字变换问题

如“将一个数字通过特定操作（如加减乘除、位运算）转换为另一个数字，求最少操作次数”。双向广搜从两个数字同时扩展，能快速找到中间转换节点。

5.3 社交网络最短路径

在社交网络中寻找两个用户的最短好友链（如“六度分隔理论”），双向广搜从两个用户同时搜索共同好友，效率远高于单方向BFS。

六、局限性

• 需要明确终点：无法用于仅知道起点、终点未知的场景（如寻找所有可达节点）。
• 实现较复杂：需要维护两个队列和访问集，处理相遇判断和路径拼接，逻辑比传统BFS复杂。
• 不适用于非最短路径问题：若问题不需要最短路径（如任意路径），双向广搜的优势不明显。

总结
双向广搜通过从两个方向同时搜索，大幅减少了传统BFS的节点访问量，尤其在长路径、大状态空间的最短路径问题中表现优异。其核心优势在于“平衡搜索进度，在中间相遇时停止”，将搜索规模从指数级压缩至平方根级别。
实现双向广搜时，需注意以下关键点：

• 维护两个方向的队列和访问集，平衡搜索进度。
• 高效生成邻接节点，减少无效扩展。
• 相遇时准确计算路径长度，必要时还原具体路径。

That’s all, thanks for reading~~
觉得有用就点个赞、收进收藏夹吧！关注我，获取更多干货～