Java双向路径搜索实现问题及完整路径获取需求

核心问题分析 #

你的代码存在几个关键问题，导致无法生成完整路径：

• 共用单个父节点映射：双向搜索需要分别维护起点→中间节点和终点→中间节点的两个父节点映射，你用同一个searchTreeParentByChild存储两个方向的关系，会导致映射混乱，覆盖正确的父节点信息。
• 反向搜索的父节点映射错误：从终点出发搜索时，你错误地将curEnd作为key、e.to()作为value存入map，正确的应该是e.to()（子节点）对应curEnd（父节点），且要存入单独的反向映射表。
• 交集判断逻辑错误：你判断的是邻接节点是否在对方的未访问队列中，这完全不准确——正确的交集判断应该是当前访问的节点是否已经被对方的搜索树标记过（即存在于对方的父映射中）。
• 找到交集后未合并路径：代码在发现交集后直接返回，没有执行路径合并的逻辑，自然无法得到从起点到终点的完整路径。

修复后的实现代码 #

我们需要拆分两个方向的父映射，修正搜索逻辑，添加路径合并步骤：

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Map;
import java.util.HashMap;
import java.util.Queue;

public class BidirectionalSearch {
    private final Graph graph;
    // 分别维护两个方向的父节点映射：子节点 → 父节点
    private Map<Vertex, Vertex> forwardParentMap;
    private Map<Vertex, Vertex> backwardParentMap;
    private List<Vertex> fullPath;

    public BidirectionalSearch(Graph graph) {
        this.graph = graph;
        this.forwardParentMap = new HashMap<>();
        this.backwardParentMap = new HashMap<>();
        this.fullPath = new ArrayList<>();
    }

    public BidirectionalSearch buildSearchTree(Vertex start, Vertex end) {
        // 重置状态
        forwardParentMap.clear();
        backwardParentMap.clear();
        fullPath.clear();

        // 校验顶点合法性
        if (!graph.vertices().containsAll(List.of(start, end))) {
            throw new IllegalArgumentException("起点或终点不在当前图中");
        }
        if (start.equals(end)) {
            fullPath.add(start);
            return this;
        }

        Queue<Vertex> forwardQueue = new ArrayDeque<>();
        Queue<Vertex> backwardQueue = new ArrayDeque<>();

        forwardQueue.add(start);
        backwardQueue.add(end);
        forwardParentMap.put(start, null);
        backwardParentMap.put(end, null);

        Vertex meetingPoint = null;

        while (!forwardQueue.isEmpty() && !backwardQueue.isEmpty() && meetingPoint == null) {
            // 正向搜索一层
            meetingPoint = expandForwardLayer(forwardQueue);
            if (meetingPoint != null) break;

            // 反向搜索一层
            meetingPoint = expandBackwardLayer(backwardQueue);
            if (meetingPoint != null) break;
        }

        // 合并路径
        if (meetingPoint != null) {
            fullPath = mergePaths(meetingPoint);
        }
        return this;
    }

    private Vertex expandForwardLayer(Queue<Vertex> queue) {
        int layerSize = queue.size();
        for (int i = 0; i < layerSize; i++) {
            Vertex current = queue.poll();
            for (Edge edge : current.edges()) {
                Vertex neighbor = edge.to();
                if (!forwardParentMap.containsKey(neighbor)) {
                    forwardParentMap.put(neighbor, current);
                    queue.add(neighbor);
                    // 检查当前邻居是否在反向搜索树中
                    if (backwardParentMap.containsKey(neighbor)) {
                        return neighbor;
                    }
                }
            }
            // 检查当前节点是否在反向搜索树中（避免漏过直接相邻的情况）
            if (backwardParentMap.containsKey(current)) {
                return current;
            }
        }
        return null;
    }

    private Vertex expandBackwardLayer(Queue<Vertex> queue) {
        int layerSize = queue.size();
        for (int i = 0; i < layerSize; i++) {
            Vertex current = queue.poll();
            for (Edge edge : current.edges()) {
                Vertex neighbor = edge.to();
                if (!backwardParentMap.containsKey(neighbor)) {
                    backwardParentMap.put(neighbor, current);
                    queue.add(neighbor);
                    // 检查当前邻居是否在正向搜索树中
                    if (forwardParentMap.containsKey(neighbor)) {
                        return neighbor;
                    }
                }
            }
            // 检查当前节点是否在正向搜索树中
            if (forwardParentMap.containsKey(current)) {
                return current;
            }
        }
        return null;
    }

    private List<Vertex> mergePaths(Vertex meetingPoint) {
        List<Vertex> forwardPath = new ArrayList<>();
        // 从交汇点回溯到起点
        Vertex current = meetingPoint;
        while (current != null) {
            forwardPath.add(current);
            current = forwardParentMap.get(current);
        }
        // 反转正向路径，得到起点→交汇点的顺序
        reverseList(forwardPath);

        // 从交汇点的父节点（反向树中）回溯到终点
        List<Vertex> backwardPath = new ArrayList<>();
        current = backwardParentMap.get(meetingPoint);
        while (current != null) {
            backwardPath.add(current);
            current = backwardParentMap.get(current);
        }

        // 合并路径
        forwardPath.addAll(backwardPath);
        return forwardPath;
    }

    private void reverseList(List<Vertex> list) {
        int left = 0;
        int right = list.size() - 1;
        while (left < right) {
            Vertex temp = list.get(left);
            list.set(left, list.get(right));
            list.set(right, temp);
            left++;
            right--;
        }
    }

    // 获取完整路径的方法
    public List<Vertex> getFullPath() {
        return new ArrayList<>(fullPath);
    }

    // 假设的Graph、Vertex、Edge接口/类定义
    public interface Graph {
        List<Vertex> vertices();
    }

    public interface Vertex {
        List<Edge> edges();
    }

    public interface Edge {
        Vertex to();
        int weight();
    }
}

关键修复说明 #

1. 拆分父映射：用forwardParentMap存储起点出发的子→父关系，backwardParentMap存储终点出发的子→父关系，避免映射冲突。
2. 分层扩展搜索：每次扩展一整层节点（而不是单个节点），确保双向搜索的层级同步，避免某一方搜索过快。
3. 正确的交集判断：在扩展每个节点时，检查当前节点/邻居是否存在于对方的父映射中，一旦找到立即返回交汇点。
4. 路径合并逻辑：从交汇点分别回溯到起点和终点，反转正向路径后与反向路径合并，得到完整的起点→终点路径。

内容的提问来源于stack exchange，提问作者Maks