基于双队列由两端交替波纹扩张，将搜索指数项从 $O(b^d)$ 瞬间收紧至 $O(2 \cdot b^{d/2})$
宽度优先搜索 (BFS) 在寻找无权图最短路径时极为经典。然而，若起点到终点距离为 $d$，分叉数为 $b$，单向 BFS 需要探索的体积为 $O(b^d)$（即以起点为中心画一个巨大圆盘）。
双向 BFS 同时自起点（正向波）与终点（反向波）两端建立独立队列交替进行 BFS 扩散。当两个探索前沿在树或图的某处碰头（交汇）时，最短路径即被确定：
int bidirectionalBFS() {
queue<int> q_f, q_b; // 正向和反向队列
q_f.push(start); vis_f[start] = 1;
q_b.push(end); vis_b[end] = 1;
while (!q_f.empty() && !q_b.empty()) {
// 核心优化：优先扩展当前节点数较小的队列 front
if (q_f.size() <= q_b.size()) {
if (expand(q_f, vis_f, vis_b)) return step;
} else {
if (expand(q_b, vis_b, vis_f)) return step;
}
}
}
bool expand(queue<int>& q, int* self_vis, int* other_vis) {
int curr = q.front(); q.pop();
for (int next : adj[curr]) {
if (other_vis[next]) {
return true; // 💥 交汇点碰头，寻路达成！
}
if (!self_vis[next]) {
self_vis[next] = 1; q.push(next);
}
}
return false;
}