双向搜索算法概述
双向搜索（bidirectional search）是一种图搜索算法，旨在寻找两个节点（起点和终点）之间的最短路径。与传统的单向搜索（如bfs或dfs）不同，双向搜索同时从起点和终点开始进行搜索，当两个搜索前沿相遇时，算法终止。这种方法通常可以显著减少需要探索的节点数量，因为搜索空间以两个方向的“半球”形式扩展，其交点通常比单个“全球”的面积小得多，从而提高搜索效率。
其核心思想是：
- 从起点S开始一个前向搜索（Forward Search）。
- 从终点T开始一个后向搜索（Backward Search）。
- 当两个搜索过程在某个节点M相遇时，即M同时被前向搜索和后向搜索访问到，则找到了一条从S到T的路径。这条路径由S到M的前向路径段和M到T的后向路径段（反向）组成。
初始实现的问题分析
在提供的Java实现中，尝试使用双向搜索来构建路径。代码片段如下：
public BidirectionalSearch buildSearchTree(Vertex start, Vertex end) {
// ... 参数校验 ...
searchTreeParentByChild.clear(); // 单个Map
Queue<Vertex> unvisitedVertexQueueFromStart = new ArrayDeque<>();
Queue<Vertex> unvisitedVertexQueueFromEnd = new ArrayDeque<>();
unvisitedVertexQueueFromStart.add(start);
unvisitedVertexQueueFromEnd.add(end);
searchTreeParentByChild.put(start, null); // 前向搜索的起点
while (!unvisitedVertexQueueFromStart.isEmpty() && !unvisitedVertexQueueFromEnd.isEmpty()) {
// 前向搜索部分
var curStart = unvisitedVertexQueueFromStart.poll();
for (var e : curStart.edges()) {
if (!searchTreeParentByChild.containsKey(e.to())) {
searchTreeParentByChild.put(e.to(), curStart); // 记录前向路径：e.to()的父节点是curStart
unvisitedVertexQueueFromStart.add(e.to());
}
}
var intersection = curStart.edges().stream()
.map(Edge::to)
.filter(unvisitedVertexQueueFromEnd::contains) // 检查交集
.findAny();
if (intersection.isPresent())
return this;
// 后向搜索部分
var curEnd = unvisitedVertexQueueFromEnd.poll();
for (var e : curEnd.edges()) {
if (!searchTreeParentByChild.containsValue(e.to())) { // 错误：这里应该是containsKey
searchTreeParentByChild.put(curEnd, e.to()); // 错误：记录后向路径的方式
unvisitedVertexQueueFromEnd.add(e.to());
}
}
intersection = curEnd.edges().stream()
.map(Edge::to)
.filter(unvisitedVertexQueueFromStart::contains) // 检查交集
.findAny();
if (intersection.isPresent())
return this;
}
return this;
}该实现存在两个主要问题：
-
单一父子映射的滥用： searchTreeParentByChild 被用于同时记录前向搜索和后向搜索的父子关系。
立即学习“Java免费学习笔记（深入）”；
- 前向搜索 searchTreeParentByChild.put(e.to(), curStart); 记录的是 子节点 -> 父节点 的关系（从start到e.to()）。
- 后向搜索 searchTreeParentByChild.put(curEnd, e.to()); 记录的是 curEnd -> e.to()。如果e.to()是curEnd的邻居，且我们希望构建从end到curEnd的路径，那么e.to()应该是curEnd的父节点。但这里的键值对是curEnd作为键，e.to()作为值，这实际上是在说curEnd是e.to()的父节点，与前向搜索的语义相同，但方向相反。更严重的是，它会覆盖或混淆前向搜索已经记录的父子关系，导致路径无法正确重构。
- searchTreeParentByChild.containsValue(e.to()) 这里的检查也是错误的，应该检查containsKey(e.to())来判断e.to()是否已经被后向搜索访问过。
路径重构缺失： 即使找到了交点，当前代码也只是简单地 return this;，并没有提供任何机制来从 searchTreeParentByChild 中提取完整的路径。由于映射被混用，即便尝试提取，也只会得到不完整的或错误的结果。
修正后的双向搜索实现策略
为了正确实现双向搜索并重构完整路径，我们需要：
-
使用两个独立的父节点映射：
- Map<Vertex, Vertex> parentFromStart; 用于记录从start出发的前向搜索路径中，每个节点的前一个节点。
- Map<Vertex, Vertex> parentFromEnd; 用于记录从end出发的后向搜索路径中，每个节点的前一个节点。
正确的交集判断： 在任一搜索步骤中，如果发现当前访问到的节点已经被另一个方向的搜索访问过，则找到了交点。
路径重构： 一旦找到交点，结合两个父节点映射来构建完整路径。
示例代码：修正后的 buildSearchTree 方法
import java.util.*;
// 假设 Vertex 和 Edge 类已定义如下：
class Vertex {
String name;
List<Edge> edges; // 出边列表，对于无向图，通常双向添加
// 构造函数、equals、hashCode、toString 等
public Vertex(String name) {
this.name = name;
this.edges = new ArrayList<>();
}
public List<Edge> edges() {
return edges;
}
public void addEdge(Edge edge) {
this.edges.add(edge);
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
Vertex vertex = (Vertex) o;
return Objects.equals(name, vertex.name);
}
@Override
public int hashCode() {
return Objects.hash(name);
}
@Override
public String toString() {
return name;
}
}
class Edge {
Vertex from;
Vertex to;
int weight;
// 构造函数、getter等
public Edge(Vertex from, Vertex to, int weight) {
this.from = from;
this.to = to;
this.weight = weight;
}
public Vertex from() {
return from;
}
public Vertex to() {
return to;
}
public int weight() {
return weight;
}
}
// 假设 Graph 类已定义
class Graph {
Set<Vertex> vertices;
// 构造函数、添加节点、添加边等
public Graph() {
this.vertices = new HashSet<>();
}
public void addVertex(Vertex v) {
vertices.add(v);
}
public Set<Vertex> vertices() {
return vertices;
}
}
public class BidirectionalSearcher {
private final Graph graph;
public BidirectionalSearcher(Graph graph) {
this.graph = graph;
}
/**
* 执行双向搜索并返回从起点到终点的路径。
*
* @param start 路径起点
* @param end 路径终点
* @return 包含路径上所有顶点的列表，如果不存在路径则返回空列表。
* @throws IllegalArgumentException 如果起点或终点不在图中。
*/
public List<Vertex> findPath(Vertex start, Vertex end) {
if (!graph.vertices().containsAll(List.of(start, end))) {
throw new IllegalArgumentException("起点或终点不在图中。");
}
if (start.equals(end)) {
return List.of(start); // 起点和终点相同，路径就是自身
}
// 记录前向搜索的父节点：child -> parent
Map<Vertex, Vertex> parentFromStart = new HashMap<>();
// 记录后向搜索的父节点：child -> parent
Map<Vertex, Vertex> parentFromEnd = new HashMap<>();
// 前向搜索队列
Queue<Vertex> queueFromStart = new ArrayDeque<>();
// 后向搜索队列
Queue<Vertex> queueFromEnd = new ArrayDeque<>();
// 初始化前向搜索
queueFromStart.add(start);
parentFromStart.put(start, null); // 起点没有父节点
// 初始化后向搜索
queueFromEnd.add(end);
parentFromEnd.put(end, null); // 终点没有父节点
Vertex meetingPoint = null; // 记录相遇点
while (!queueFromStart.isEmpty() && !queueFromEnd.isEmpty() && meetingPoint == null) {
// 执行前向搜索一步
meetingPoint = searchStep(queueFromStart, parentFromStart, parentFromEnd);
if (meetingPoint != null) break;
// 执行后向搜索一步
meetingPoint = searchStep(queueFromEnd, parentFromEnd, parentFromStart);
if (meetingPoint != null) break;
}
if (meetingPoint == null) {
return List.of(); // 未找到路径
}
// 重构路径
return reconstructPath(start, end, meetingPoint, parentFromStart, parentFromEnd);
}
/**
* 单步搜索逻辑，用于前向或后向搜索。
*
* @param currentQueue 当前搜索方向的队列
* @param currentParents 当前搜索方向的父节点映射 (child -> parent)
* @param otherParents 另一个搜索方向的父节点映射 (child -> parent)
* @return 如果找到交点则返回交点Vertex，否则返回null
*/
private Vertex searchStep(Queue<Vertex> currentQueue,
Map<Vertex, Vertex> currentParents,
Map<Vertex, Vertex> otherParents) {
if (currentQueue.isEmpty()) {
return null;
}
Vertex current = currentQueue.poll();
// 遍历当前节点的邻居
for (Edge edge : current.edges()) {
Vertex neighbor = edge.to(); // 假设边是 from -> to
// 如果邻居未被当前搜索方向访问过
if (!currentParents.containsKey(neighbor)) {
currentParents.put(neighbor, current); // 记录父节点
currentQueue.add(neighbor);
// 检查是否与另一个搜索方向相遇
if (otherParents.containsKey(neighbor)) {
return neighbor; // 找到交点
}
}
}
return null;
}
/**
* 从两个父节点映射和交点重构完整路径。
*
* @param start 起点
* @param end 终点
* @param meetingPoint 相遇点
* @param parentFromStart 前向搜索的父节点映射
* @param parentFromEnd 后向搜索的父节点映射
* @return 完整的路径列表
*/
private List<Vertex> reconstructPath(Vertex start, Vertex end, Vertex meetingPoint,
Map<Vertex, Vertex> parentFromStart,
Map<Vertex, Vertex> parentFromEnd) {
List<Vertex> path = new LinkedList<>(); // 使用 LinkedList 便于在头部 
