实现Java双向路径搜索的正确方法

import java.util.*;

public class BidirectionalSearch {

    private final Graph graph;
    private final Map<Vertex, Vertex> forwardSearchTree = new HashMap<>();
    private final Map<Vertex, Vertex> backwardSearchTree = new HashMap<>();

    public BidirectionalSearch(Graph graph) {
        this.graph = graph;
    }

    public Optional<List<Vertex>> findPath(Vertex start, Vertex end) {
        if (!graph.vertices().containsAll(List.of(start, end))) {
            throw new IllegalArgumentException("start or stop vertices not from this graph");
        }

        if (start.equals(end)) {
            return Optional.of(List.of(start));
        }

        forwardSearchTree.clear();
        backwardSearchTree.clear();

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

        forwardQueue.add(start);
        backwardQueue.add(end);

        forwardSearchTree.put(start, null);
        backwardSearchTree.put(end, null);

        Vertex intersection = null;

        while (!forwardQueue.isEmpty() && !backwardQueue.isEmpty()) {
            // Forward search
            Vertex currentForward = forwardQueue.poll();
            for (Edge edge : currentForward.edges()) {
                Vertex neighbor = edge.to();
                if (!forwardSearchTree.containsKey(neighbor)) {
                    forwardSearchTree.put(neighbor, currentForward);
                    forwardQueue.add(neighbor);
                    if (backwardSearchTree.containsKey(neighbor)) {
                        intersection = neighbor;
                        break;
                    }
                }
            }
            if (intersection != null) break;

            // Backward search
            Vertex currentBackward = backwardQueue.poll();
            for (Edge edge : currentBackward.edges()) {
                Vertex neighbor = edge.to();
                if (!backwardSearchTree.containsKey(neighbor)) {
                    backwardSearchTree.put(neighbor, currentBackward);
                    backwardQueue.add(neighbor);
                    if (forwardSearchTree.containsKey(neighbor)) {
                        intersection = neighbor;
                        break;
                    }
                }
            }
            if (intersection != null) break;
        }

        if (intersection == null) {
            return Optional.empty(); // No path found
        }

        // Reconstruct the path
        List<Vertex> forwardPath = reconstructPath(forwardSearchTree, start, intersection);
        List<Vertex> backwardPath = reconstructPath(backwardSearchTree, end, intersection);
        Collections.reverse(backwardPath); // Reverse the backward path

        List<Vertex> fullPath = new ArrayList<>(forwardPath);
        fullPath.addAll(backwardPath.subList(1, backwardPath.size())); // Avoid duplicate intersection vertex

        return Optional.of(fullPath);
    }

    private List<Vertex> reconstructPath(Map<Vertex, Vertex> searchTree, Vertex start, Vertex end) {
        List<Vertex> path = new ArrayList<>();
        Vertex current = end;
        while (current != null) {
            path.add(current);
            current = searchTree.get(current);
        }
        Collections.reverse(path);
        return path;
    }


    // 示例Graph和Vertex/Edge类的定义 (需要根据你的实际情况调整)
    interface Graph {
        Set<Vertex> vertices();
    }

    interface Vertex {
        Set<Edge> edges();
    }

    interface Edge {
        Vertex to();
    }
}