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;
}

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 便于在头部