算法讲解063 必备 双向广搜

来源：算法讲解063【必备】双向广搜　·　2026-10-28

依据：视频字幕 2000 字

一句话概括

双向广搜（Bidirectional BFS）是从起点和终点同时做宽度优先搜索（BFS），每次只扩展当前队列更小的一侧，两侧在中间相遇时即得最短距离；核心价值是把搜索空间从指数级压到约平方根级。

它解决什么问题

• 用途一（小优化）：普通 BFS 从 S 单向展开，层数越深节点数爆炸（7 → 20 → 50 → …）。双向广搜每次挑「当前待扩展节点更少」的一侧展开，两侧在中线相遇，总扩展量显著变小。
• 用途二（主要用途，特征极明显）：状态空间「完全展开代价不可接受，但一半深度的展开量可以接受」的题。典型如单词接龙（每次改一个字符）、八数码/九数码、魔板、推箱子类状态搜索。单向 BFS 到目标深度 d 要展开 b^d 个状态，双向只需约 2·b^(d/2)。

基础知识（前置概念，用大白话解释）

• 宽度优先搜索（Breadth-First Search, BFS）：用队列一层一层往外扩。在边权全为 1 的无向图上，第一次访问到某点时的层数就是最短距离。
• 无向图：边没有方向，A 到 B 的距离等于 B 到 A 的距离。双向广搜成立的前提就是「从 S 搜到 E 的最短路 = 从 E 搜到 S 的最短路」，所以两侧可以同时搜。
• 状态 / 状态转移：把「当前局面」编码成一个可哈希的值（字符串、整数、数组），一步操作得到新状态。BFS 就是在状态图上跑。
• 队列（Queue）：先进先出，保证按层扩展。
• 哈希表（Hash Map / Hash Set）：记录「某状态在第几层被访问过」，用于判重和算距离。竞赛里常用 unordered_map 或手写哈希。
• 递归 / 完全展开：这里指把整个状态图搜完。判断「能不能双向」靠的是数据量拆解：单向全展开不可行、半深度展开可行 → 上双向。

原理（为什么这么做是对的，尽量给直觉）

设 S 到 E 的最短距离为 d。

1. 正确性：图是无向的，S→E 的每条最短路反过来就是 E→S 的最短路。两侧 BFS 各自按层扩展，当某个状态同时被两侧访问过，说明存在一条 S→x→E 的路，长度 = distS[x] + distE[x]。在所有「两侧都访问过的状态」里取最小值，就是 d。
2. 为什么每次扩小的一侧：BFS 第 k 层的节点数大致是 b^k（b 为分支因子）。总工作量 ≈ 两侧各自展开到相遇深度的节点数之和。让两侧深度尽量均衡（各约 d/2），总量 ≈ b^(d/2) + b^(d/2)，远小于单向的 b^d。每次挑队列小的那侧扩，就是让两侧「进度」尽量同步、避免一侧先爆。
3. 为什么相遇即最优：BFS 按层扩展，队列里的层数单调不减。两侧都在「由近及远」地铺，第一次出现交集时，交集中的最小 distS+distE 就是最短。实践中更稳的写法是：每扩完一层就检查一次答案，而不是一遇到交集就立刻返回（见易错点）。

步骤（编号，可照着写）

以「求 S 到 E 的最短步数」为例，状态用可哈希类型表示：

1. 特判 S == E，直接返回 0。
2. 建两个队列 qS, qE，两个哈希表 distS, distE（记录状态 → 层数）。distS[S]=0, distE[E]=0，各自入队。
3. 循环直到某一侧队列为空：

1. 选 qS.size() <= qE.size() 的那一侧作为「当前扩展侧」。

2. 记下当前侧本层的节点数 sz = 当前队列大小（只扩这一层，保证层数正确）。

3. 对 sz 个节点逐个弹出，枚举所有一步转移得到 nxt：

- 若 nxt 已在本侧 dist 中，跳过（判重）。

- 记录本侧距离 = 当前层 + 1，入队。

- 若 nxt 在另一侧 dist 中出现过，说明相遇，用 dist本侧[nxt] + dist另一侧[nxt] 更新答案（注意：不要立刻 return，见易错点；若题目保证第一次相遇即最优且你按层扩，也可直接返回，但要写对）。

4. 本层扩完后，若答案已被更新，可返回（按层扩展下，本层产生的候选已是最优层数组合）。

1. 队列空仍未相遇 → 无解（返回 -1 或题目要求的标记）。

关键点：每次只扩一层，且扩的是「队列更小」的那一侧；两侧距离表分开维护。

样例（一个具体小例子，带每步变化）

图：S - a - b - E，另有一条长链 S - c - d - f - g - E（边权均为 1）。真实最短路 S→a→b→E，长度 3。

初始：qS=[S] distS{S:0}，qE=[E] distE{E:0}。

| 轮次 | 选侧（队列小） | 扩展层 | 新访问 | 相遇？ | 答案 |

|---|---|---|---|---|---|

| 1 | qS(1) vs qE(1)，选 S | S→{a,c} | distS{a:1,c:1} | 无 | — |

| 2 | qS(2) vs qE(1)，选 E | E→{b,g} | distE{b:1,g:1} | 无 | — |

| 3 | qS(2) vs qE(2)，选 S | a→{b}, c→{d} | distS{b:2,d:2} | b 在 distE 中！ | 2+1=3 |

| 4 | 本层扩完，返回 | | | | 3 |

对比单向 BFS：从 S 出发要扩到第 3 层才碰到 E，中间会把 c,d,f,g 全展开；双向只扩了 2 层就相遇。

代码（Python 一份：好读、用于理解；C++ 一份：竞赛风，能直接抄进比赛，带注释，不用玄学宏）

Python（好读版，以「单词接龙」抽象为例）

from collections import deque

def bidirectional_bfs(start, end, neighbors):
    """neighbors(state) -> 可迭代的一步可达状态集合"""
    if start == end:
        return 0
    qs, qe = deque([start]), deque([end])
    ds, de = {start: 0}, {end: 0}

    while qs and qe:
        # 每次扩队列更小的一侧
        if len(qs) <= len(qe):
            q, d_this, d_other = qs, ds, de
        else:
            q, d_this, d_other = qe, de, ds

        sz = len(q)                    # 只扩本层
        for _ in range(sz):
            cur = q.popleft()
            for nxt in neighbors(cur):
                if nxt in d_this:
                    continue
                d_this[nxt] = d_this[cur] + 1
                if nxt in d_other:     # 相遇
                    return d_this[nxt] + d_other[nxt]
                q.append(nxt)
    return -1

说明：上面「一相遇就返回」在按层扩展且两侧都只扩一层的前提下是正确的（第一次相遇的层数和最小）。若你的实现不是严格按层（比如一次扩多个节点但没锁层），必须改成「本层扩完再取最小」，见易错点。

C++（竞赛风，单词接龙模板，可直接抄）

#include <bits/stdc++.h>
using namespace std;

// 单词接龙：每次改一个字符，字符集为小写字母；返回最短步数，不可达返回 0
// 数据规模：单词长度 <= 10，词表 <= 5000（典型 LC 127 规模）
int ladderLength(const string& beginWord, const string& endWord,
                 const vector<string>& wordList) {
    unordered_set<string> dict(wordList.begin(), wordList.end());
    if (!dict.count(endWord)) return 0;
    if (beginWord == endWord) return 0;

    unordered_map<string, int> ds, de;
    queue<string> qs, qe;
    ds[beginWord] = 0; qs.push(beginWord);
    de[endWord]   = 0; qe.push(endWord);

    auto expand = [&](queue<string>& q, unordered_map<string, int>& dthis,
                      unordered_map<string, int>& dother) -> int {
        int sz = (int)q.size();                 // 只扩本层
        for (int i = 0; i < sz; ++i) {
            string cur = q.front(); q.pop();
            string nxt = cur;
            for (char& c : nxt) {
                char old = c;
                for (char ch = 'a'; ch <= 'z'; ++ch) {
                    if (ch == old) continue;
                    c = ch;
                    if (!dict.count(nxt)) continue;
                    if (dthis.count(nxt)) continue;
                    dthis[nxt] = dthis[cur] + 1;
                    if (dother.count(nxt))
                        return dthis[nxt] + dother[nxt];
                    q.push(nxt);
                }
                c = old;
            }
        }
        return -1;                              // 本层未相遇
    };

    while (!qs.empty() && !qe.empty()) {
        int ans;
        if (qs.size() <= qe.size())
            ans = expand(qs, ds, de);
        else
            ans = expand(qe, de, ds);
        if (ans != -1) return ans;
    }
    return 0;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    // 示例
    vector<string> wl = {"hot","dot","dog","lot","log","cog"};
    cout << ladderLength("hit", "cog", wl) << "\n"; // 5
    return 0;
}

复杂度

• 时间：设分支因子 b、最短距离 d。单向 BFS 最坏 O(b^d)；双向约 O(b^(d/2))（更精确是两侧展开到相遇深度的节点数之和）。每次扩展还要枚举一步转移（如单词接龙是 L·26，L 为词长）。
• 空间：两个哈希表 + 两个队列，量级同时间，约 O(b^(d/2))。
• 最好/平均/最坏：最好 S 与 E 相邻（O(1) 特判或一两层）；平均取决于图结构；最坏即上面公式。
• 常数：哈希表操作常数不小，unordered_map 在 1e5~1e6 状态量下建议 reserve 或用 gp_hash_table/手写哈希；字符串状态建议先编码成整数（如把单词映射成 id）再搜，能显著降常数。

竞赛里什么时候用（看到什么题面特征就该想到它）

• 题面出现「每次只能改变一个字符 / 一个位置 / 一次操作」，求最少步数，且状态空间巨大（单向 BFS 会 MLE/TLE）。
• 状态可逆（操作可逆，图无向），如八数码、魔板、推箱子、倒水问题。
• 数据量拆解结论：全展开不可行，但深度一半的展开量可行（这是判断要不要上双向的硬标准）。
• 求「最短」而非「所有方案」时优先双向；求所有最短路径（如单词接龙 II）双向会麻烦很多，一般仍用单向 BFS + 预处理。

竞赛模板（C++，可直接背下来的写法；变量名清楚）

#include <bits/stdc++.h>
using namespace std;

// 通用双向 BFS 骨架：状态用 int 编码，neighbors 返回一步可达状态
// distS/distE 用 unordered_map 或（状态范围小时）数组
int bidirectionalBFS(int start, int target,
                     const function<vector<int>(int)>& neighbors) {
    if (start == target) return 0;
    unordered_map<int,int> distS, distE;
    queue<int> qS, qE;
    distS[start] = 0; qS.push(start);
    distE[target] = 0; qE.push(target);

    auto expand = [&](queue<int>& q, unordered_map<int,int>& dThis,
                      unordered_map<int,int>& dOther) -> int {
        int sz = (int)q.size();
        for (int i = 0; i < sz; ++i) {
            int cur = q.front(); q.pop();
            for (int nxt : neighbors(cur)) {
                if (dThis.count(nxt)) continue;
                dThis[nxt] = dThis[cur] + 1;
                if (dOther.count(nxt)) return dThis[nxt] + dOther[nxt];
                q.push(nxt);
            }
        }
        return -1;
    };

    while (!qS.empty() && !qE.empty()) {
        int ans = (qS.size() <= qE.size())
                    ? expand(qS, distS, distE)
                    : expand(qE, distE, distS);
        if (ans != -1) return ans;
    }
    return -1; // 不可达
}

边界与易错点（WA 的常见原因，越具体越好）

1. 没锁层：一次扩了「队列里所有节点」而不是「本层 sz 个节点」，导致层数错乱、相遇时距离不是最短。必须 sz = q.size() 后只弹 sz 个。
2. 一相遇就返回但没按层扩：若实现不是严格按层，第一次相遇的 distS+distE 不一定最小，应在本层扩完后取所有候选的最小值。
3. 两侧距离表混用：判重必须查本侧表，相遇查另一侧表，写反会死循环或算错。
4. start == end 没特判：有的题要求返回 0，有的返回 1（如单词接龙若 begin==end 且合法），按题意。
5. 终点不在字典里：单词接龙类题，endWord 不在词表直接无解，先判。
6. 多测清空：全局哈希表/队列/数组在多组数据间必须清空，否则串数据。
7. unordered_map 被卡：出题人可能构造哈希冲突，竞赛里对状态量大的题用 reserve 或换 map/手写哈希/离散化后数组。
8. 状态编码溢出：把多维状态压成 int 时注意位数，必要时用 long long 或 pair 哈希。
9. 无向性假设：双向 BFS 要求操作可逆。若操作不可逆（有向图），不能直接双向，需谨慎。
10. 队列空判断：循环条件写 while(!qS.empty() && !qE.empty())，一侧空了就无解。

同类题 / 变形

• 单词接龙（LC 127）：本题原型，改字符，双向 BFS 标准应用。
• 单词接龙 II（LC 126）：求所有最短路径，双向麻烦，一般单向 BFS 建图 + DFS。
• 八数码 / 九数码：状态编码（康托展开或整数），双向 BFS 或 A*；双向时注意状态可逆。
• 魔板（Luogu P2730）：状态为排列，双向 BFS 经典。
• 倒水问题：两杯水互相倒，状态 (a,b)，双向 BFS。
• 变形：双向 DFS / 折半搜索（Meet in the Middle）：思路同源——从两端搜、中间合并，适用于「全展开不可行、半量可行」的组合计数/最优化题。
• 变形：双向 BFS 求路径条数：相遇时累加 distS+distE 等于最短的路径数，需在本层扩完后统计，不能提前返回。

常见坑

• 用 list/map 存队列和距离表，常数爆炸，1e5 以上直接 TLE；用 vector/queue/unordered_map（带 reserve）。
• 忘记 ios::sync_with_stdio(false); cin.tie(nullptr);，大数据输入慢。
• 状态是字符串时每次拼接产生大量临时对象，先映射成整数 id。
• 双向 BFS 不是万能的：若分支因子很小（如线性链），双向收益不大；若状态不可逆，不能用。
• 求「所有最短路」时双向 BFS 的合并逻辑复杂，容易漏算/重算，竞赛里优先单向。

拓展（变体、实际用途、面试常问）

• **A\*（A-Star）**：双向 BFS 的「带启发」版本，用估价函数剪枝，八数码常用「曼哈顿距离」估价。
• Meet in the Middle：双向思想在子集和、折半枚举、密码学中间相遇攻击里的体现。
• 实际用途：社交网络六度分隔（双向 BFS 找两人最短关系链）、路由、游戏 AI 寻路、拼图求解。
• 面试常问：「为什么双向 BFS 更快？」「什么时候不能用双向 BFS？」「如何保证第一次相遇就是最短？」——答案分别是指数降平方根、操作不可逆/求所有路径、按层扩展 + 本层扩完取最小。

自测 3 题（题目 + 折叠答案）

题 1：单词接龙，begin="hit", end="cog", wordList=["hot","dot","dog","lot","log","cog"]，求最短转换序列长度（含首尾单词数）。