算法概述
双向搜索（Bidirectional Search）是一种从起点和终点同时向对方搜索的策略，广泛应用于无权图最短路径、字符串编辑距离、拼图求解等场景。相较于单向BFS，双向搜索将时间复杂度从O(b^d)降至O(b^(d/2))，其中b为分支因子，d为最短路径长度。本文用Java实现双向BFS，并展示其在迷宫最短路径问题中的应用。
核心原理
单向BFS从起点向外扩展搜索树，而双向BFS同时维护两个搜索前沿（frontier）：一个从起点正向扩展，一个从终点反向扩展。当两个前沿相遇时，即找到最短路径。关键在于两个搜索交替进行（通常选择队列较小的一方扩展），以保证两棵搜索树的大小均衡。
完整Java实现
import java.util.*;
public class BidirectionalSearch {
/**
* 双向BFS求解无权图最短路径
* @param graph 邻接表表示的无权图
* @param start 起点
* @param end 终点
* @return 最短路径节点列表，不可达返回空列表
*/
public static List<Integer> bidirectionalBFS(
Map<Integer, List<Integer>> graph, int start, int end) {
if (start == end) return Collections.singletonList(start);
if (!graph.containsKey(start) || !graph.containsKey(end)) return Collections.emptyList();
// 两个方向的访问集合与前驱映射
Set<Integer> visitedFromStart = new HashSet<>();
Set<Integer> visitedFromEnd = new HashSet<>();
Map<Integer, Integer> parentFromStart = new HashMap<>();
Map<Integer, Integer> parentFromEnd = new HashMap<>();
Queue<Integer> queueStart = new LinkedList<>();
Queue<Integer> queueEnd = new LinkedList<>();
queueStart.offer(start);
queueEnd.offer(end);
visitedFromStart.add(start);
visitedFromEnd.add(end);
Integer meetingPoint = null;
while (!queueStart.isEmpty() && !queueEnd.isEmpty()) {
// 总是扩展队列较小的一方，保持两棵搜索树平衡
if (queueStart.size() <= queueEnd.size()) {
meetingPoint = expandFrontier(graph, queueStart, visitedFromStart,
visitedFromEnd, parentFromStart);
} else {
meetingPoint = expandFrontier(graph, queueEnd, visitedFromEnd,
visitedFromStart, parentFromEnd);
}
if (meetingPoint != null) break;
}
if (meetingPoint == null) return Collections.emptyList();
return reconstructPath(meetingPoint, parentFromStart, parentFromEnd);
}
/**
* 扩展一个搜索前沿，检查是否与对方前沿相交
*/
private static Integer expandFrontier(
Map<Integer, List<Integer>> graph,
Queue<Integer> queue,
Set<Integer> visitedSelf,
Set<Integer> visitedOther,
Map<Integer, Integer> parent) {
int size = queue.size();
for (int i = 0; i < size; i++) {
int curr = queue.poll();
for (int neighbor : graph.getOrDefault(curr, Collections.emptyList())) {
if (visitedOther.contains(neighbor)) {
parent.put(neighbor, curr); // 记录连接点
return neighbor;
}
if (!visitedSelf.contains(neighbor)) {
visitedSelf.add(neighbor);
parent.put(neighbor, curr);
queue.offer(neighbor);
}
}
}
return null;
}
/**
* 从交汇点重构完整路径
*/
private static List<Integer> reconstructPath(
int meetingPoint,
Map<Integer, Integer> parentFromStart,
Map<Integer, Integer> parentFromEnd) {
List<Integer> path = new ArrayList<>();
// 从交汇点回溯到起点
Integer curr = meetingPoint;
while (curr != null) {
path.add(curr);
curr = parentFromStart.get(curr);
}
Collections.reverse(path);
// 从交汇点的下一节点回溯到终点
curr = parentFromEnd.get(meetingPoint);
while (curr != null) {
path.add(curr);
curr = parentFromEnd.get(curr);
}
return path;
}
/**
* 迷宫最短路径：0为通路，1为障碍
*/
public static List<int[]> mazeShortestPath(int[][] maze, int[] start, int[] end) {
int rows = maze.length, cols = maze[0].length;
if (start[0] == end[0] && start[1] == end[1])
return Collections.singletonList(start);
int[][] dirs = {{-1,0},{1,0},{0,-1},{0,1}};
Set<String> visitedStart = new HashSet<>();
Set<String> visitedEnd = new HashSet<>();
Map<String, String> parentStart = new HashMap<>();
Map<String, String> parentEnd = new HashMap<>();
Queue<String> qStart = new LinkedList<>();
Queue<String> qEnd = new LinkedList<>();
String sKey = start[0]+","+start[1];
String eKey = end[0]+","+end[1];
qStart.offer(sKey); qEnd.offer(eKey);
visitedStart.add(sKey); visitedEnd.add(eKey);
String meet = null;
while (!qStart.isEmpty() && !qEnd.isEmpty()) {
Queue<String> q = qStart.size() <= qEnd.size() ? qStart : qEnd;
Set<String> vis = q == qStart ? visitedStart : visitedEnd;
Set<String> otherVis = q == qStart ? visitedEnd : visitedStart;
Map<String, String> par = q == qStart ? parentStart : parentEnd;
int sz = q.size();
for (int i = 0; i < sz; i++) {
String key = q.poll();
String[] parts = key.split(",");
int r = Integer.parseInt(parts[0]), c = Integer.parseInt(parts[1]);
for (int[] d : dirs) {
int nr = r + d[0], nc = c + d[1];
if (nr < 0 || nr >= rows || nc < 0 || nc >= cols || maze[nr][nc] == 1) continue;
String nKey = nr + "," + nc;
if (otherVis.contains(nKey)) {
par.put(nKey, key);
meet = nKey;
break;
}
if (!vis.contains(nKey)) {
vis.add(nKey);
par.put(nKey, key);
q.offer(nKey);
}
}
if (meet != null) break;
}
if (meet != null) break;
}
if (meet == null) return Collections.emptyList();
return reconstructMazePath(meet, parentStart, parentEnd);
}
private static List<int[]> reconstructMazePath(String meet,
Map<String, String> ps, Map<String, String> pe) {
List<int[]> path = new ArrayList<>();
String curr = meet;
while (curr != null) {
String[] p = curr.split(",");
path.add(new int[]{Integer.parseInt(p[0]), Integer.parseInt(p[1])});
curr = ps.get(curr);
}
Collections.reverse(path);
curr = pe.get(meet);
while (curr != null) {
String[] p = curr.split(",");
path.add(new int[]{Integer.parseInt(p[0]), Integer.parseInt(p[1])});
curr = pe.get(curr);
}
return path;
}
public static void main(String[] args) {
// 图最短路径测试
Map<Integer, List<Integer>> graph = new HashMap<>();
graph.put(0, Arrays.asList(1, 2));
graph.put(1, Arrays.asList(0, 3, 4));
graph.put(2, Arrays.asList(0, 5));
graph.put(3, Arrays.asList(1, 6));
graph.put(4, Arrays.asList(1, 5, 6));
graph.put(5, Arrays.asList(2, 4, 7));
graph.put(6, Arrays.asList(3, 4, 7));
graph.put(7, Arrays.asList(5, 6));
List<Integer> path = bidirectionalBFS(graph, 0, 7);
System.out.println("双向BFS最短路径: " + path);
// 迷宫测试
int[][] maze = {
{0,0,1,0,0},
{0,0,1,0,0},
{0,0,0,0,1},
{0,1,1,0,0},
{0,0,0,0,0}
};
List<int[]> mazePath = mazeShortestPath(maze, new int[]{0,0}, new int[]{4,4});
System.out.println("迷宫双向BFS路径长度: " + mazePath.size());
for (int[] p : mazePath) System.out.print("("+p[0]+","+p[1]+") ");
}
}
复杂度分析
| 指标 | 单向BFS | 双向BFS |
|---|---|---|
| 时间复杂度 | O(b^d) | O(b^(d/2)) |
| 空间复杂度 | O(b^d) | O(b^(d/2)) |
| 实际扩展节点数 | ~b^d | ~2*b^(d/2) |
当d=10、b=3时，单向BFS约扩展59049个节点，双向BFS仅约2*243=486个节点，效率提升约120倍。
应用场景
- 社交网络关系链：计算两个人之间的最短好友关系链
- 拼图解谜：15拼图、魔方等状态空间搜索问题
- 路由规划：网络层最短路径、游戏AI寻路
- 字符串相似度：编辑距离计算中的双向动态规划
- 生物信息学：DNA序列比对中的双向前缀搜索
