双向路径搜索算法的Java实现及路径构建详解

import java.util.*;

public class BidirectionalSearch {

    private final Graph graph;
    private final Map<Vertex, Vertex> searchTreeParentByChildFromStart = new HashMap<>();
    private final Map<Vertex, Vertex> searchTreeParentByChildFromEnd = new HashMap<>();

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

    public BidirectionalSearch buildSearchTree(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 this;

        searchTreeParentByChildFromStart.clear();
        searchTreeParentByChildFromEnd.clear();

        Queue<Vertex> unvisitedVertexQueueFromStart = new ArrayDeque<>();
        Queue<Vertex> unvisitedVertexQueueFromEnd = new ArrayDeque<>();

        unvisitedVertexQueueFromStart.add(start);
        unvisitedVertexQueueFromEnd.add(end);

        searchTreeParentByChildFromStart.put(start, null);
        searchTreeParentByChildFromEnd.put(end, null);

        Vertex intersectionVertex = null;

        while (!unvisitedVertexQueueFromStart.isEmpty() && !unvisitedVertexQueueFromEnd.isEmpty()) {
            Vertex curStart = unvisitedVertexQueueFromStart.poll();

            for (Edge e : curStart.edges()) {
                Vertex neighbor = e.to();
                if (!searchTreeParentByChildFromStart.containsKey(neighbor)) {
                    searchTreeParentByChildFromStart.put(neighbor, curStart);
                    unvisitedVertexQueueFromStart.add(neighbor);

                    if (searchTreeParentByChildFromEnd.containsKey(neighbor)) {
                        intersectionVertex = neighbor;
                        break; // Found intersection
                    }
                }
            }

            if (intersectionVertex != null) break;


            Vertex curEnd = unvisitedVertexQueueFromEnd.poll();

            for (Edge e : curEnd.edges()) {
                Vertex neighbor = e.to();
                if (!searchTreeParentByChildFromEnd.containsKey(neighbor)) {
                    searchTreeParentByChildFromEnd.put(neighbor, curEnd);
                    unvisitedVertexQueueFromEnd.add(neighbor);

                    if (searchTreeParentByChildFromStart.containsKey(neighbor)) {
                        intersectionVertex = neighbor;
                        break; // Found intersection
                    }
                }
            }

            if (intersectionVertex != null) break;

        }

        return this;
    }

    public List<Vertex> getPath(Vertex start, Vertex end) {
        buildSearchTree(start, end);
        Vertex intersection = findIntersection(start, end);

        if (intersection == null) {
            return Collections.emptyList(); // No path found
        }

        List<Vertex> pathToIntersectionFromStart = buildPath(searchTreeParentByChildFromStart, intersection);
        List<Vertex> pathToIntersectionFromEnd = buildPath(searchTreeParentByChildFromEnd, intersection);

        Collections.reverse(pathToIntersectionFromEnd); // Reverse the end path

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

        return fullPath;
    }

    private Vertex findIntersection(Vertex start, Vertex end) {
        for (Vertex vertex : searchTreeParentByChildFromStart.keySet()) {
            if (searchTreeParentByChildFromEnd.containsKey(vertex)) {
                return vertex;
            }
        }
        return null;
    }

    private List<Vertex> buildPath(Map<Vertex, Vertex> searchTree, Vertex intersection) {
        List<Vertex> path = new LinkedList<>();
        Vertex current = intersection;

        while (current != null) {
            path.add(0, current); // Add to the beginning to reverse the path
            current = searchTree.get(current);
        }

        return path;
    }

    // Example Graph, Vertex and Edge classes (replace with your actual implementations)
    static class Graph {
        private final Set<Vertex> vertices = new HashSet<>();

        public void addVertex(Vertex vertex) {
            vertices.add(vertex);
        }

        public Set<Vertex> vertices() {
            return vertices;
        }
    }

    static class Vertex {
        private final String name;
        private final List<Edge> edges = new ArrayList<>();

        public Vertex(String name) {
            this.name = name;
        }

        public String getName() {
            return name;
        }

        public void addEdge(Edge edge) {
            edges.add(edge);
        }

        public List<Edge> edges() {
            return edges;
        }

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

    static class Edge {
        private final Vertex from;
        private final Vertex to;
        private final int weight;

        public Edge(Vertex from, Vertex to, int weight) {
            this.from = from;
            this.to = to;
            this.weight = weight;
        }

        public Vertex to() {
            return to;
        }
    }

    public static void main(String[] args) {
        // Example Usage
        Graph graph = new Graph();
        Vertex start = new Vertex("A");
        Vertex b = new Vertex("B");
        Vertex c = new Vertex("C");
        Vertex end = new Vertex("D");

        graph.addVertex(start);
        graph.addVertex(b);
        graph.addVertex(c);
        graph.addVertex(end);

        start.addEdge(new Edge(start, b, 1));
        b.addEdge(new Edge(b, c, 1));
        c.addEdge(new Edge(c, end, 1));
        end.addEdge(new Edge(end, c, 1));

        BidirectionalSearch search = new BidirectionalSearch(graph);
        List<Vertex> path = search.getPath(start, end);

        if (!path.isEmpty()) {
            System.out.println("Path found: ");
            for (Vertex vertex : path) {
                System.out.print(vertex.getName() + " ");
            }
            System.out.println();
        } else {
            System.out.println("No path found.");
        }
    }
}