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 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 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 meetNode = null;

        while (!forwardQueue.isEmpty() && !backwardQueue.isEmpty()) {
            Vertex forwardNode = forwardQueue.poll();
            if (expandForward(forwardNode, forwardQueue)) {
                meetNode = findIntersection(forwardSearchTree.keySet(), backwardSearchTree.keySet());
                if (meetNode != null) break;
            }

            Vertex backwardNode = backwardQueue.poll();
            if (expandBackward(backwardNode, backwardQueue)) {
                meetNode = findIntersection(forwardSearchTree.keySet(), backwardSearchTree.keySet());
                if (meetNode != null) break;
            }
        }

        if (meetNode == null) {
            return null; // No path found
        }

        return constructPath(start, end, meetNode);
    }

    private boolean expandForward(Vertex node, Queue<Vertex> queue) {
        for (Edge edge : node.edges()) {
            Vertex neighbor = edge.to();
            if (!forwardSearchTree.containsKey(neighbor)) {
                forwardSearchTree.put(neighbor, node);
                queue.add(neighbor);
                return true;
            }
        }
        return false;
    }

    private boolean expandBackward(Vertex node, Queue<Vertex> queue) {
        for (Edge edge : graph.getIncomingEdges(node)) { // Assuming you have a method to get incoming edges
            Vertex neighbor = edge.from();
            if (!backwardSearchTree.containsKey(neighbor)) {
                backwardSearchTree.put(neighbor, node);
                queue.add(neighbor);
                return true;
            }
        }
        return false;
    }

    private Vertex findIntersection(Set<Vertex> forwardSet, Set<Vertex> backwardSet) {
        for (Vertex vertex : forwardSet) {
            if (backwardSet.contains(vertex)) {
                return vertex;
            }
        }
        return null;
    }

    private List<Vertex> constructPath(Vertex start, Vertex end, Vertex meetNode) {
        List<Vertex> forwardPath = new ArrayList<>();
        Vertex current = meetNode;
        while (current != null) {
            forwardPath.add(current);
            current = forwardSearchTree.get(current);
        }
        Collections.reverse(forwardPath);

        List<Vertex> backwardPath = new ArrayList<>();
        current = meetNode;
        while (current != null) {
            backwardPath.add(current);
            current = backwardSearchTree.get(current);
        }
        // Remove the meeting node from the backward path to avoid duplication
        backwardPath.remove(0);
        forwardPath.addAll(backwardPath);

        return forwardPath;
    }

    // Assuming you have a Graph class, Vertex class, and Edge class defined
    // and a method in Graph class to get incoming edges of a vertex.
    interface Graph {
        Set<Vertex> vertices();
        List<Edge> getIncomingEdges(Vertex vertex);
    }

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

    interface Edge {
        Vertex to();
        Vertex from();
    }
}