Bidirektionale Suche Implementierung für Grafik

Question

Der Versuch, bidirektionale Suche nach Grafik zu implementieren, aber viele Male fehlgeschlagen, es zu tun. Wie ich verstehe, sollte ich 2 Breadth First Searches für "Start" und "End" Vertexes irgendwie zusammenführen. Der Basisfall liegt vor, wenn beide Suchvorgänge denselben Vertex gefunden haben. Können Sie mir ein Codebeispiel (in Java oder JavaScript, wenn möglich) zur Verfügung stellen oder mit Code für die bidirektionale Suche verknüpfen?

Answer 1

Angenommen, Sie Knoten wie dieses:

public static class Node { 
    private final T data; 
    private final Set<Node> adjacent = new HashSet<Node>(); 

    public Set<Node> getAdjacent() { 
     return adjacent; 
    } 

    public Node(T data) { 
     this.data = data; 
    } 

    public T getData() { 
     return data; 
    } 

    // returns if the node was added, false if already there 
    public boolean addAdjacent(Node node) { 
     return adjacent.add(node); 
    } 

    // returns true if any were added 
    public boolean addAdjacents(Set<Node> nodes) { 
     return adjacent.addAll(nodes); 
    } 
} 

Dann denke ich, Sie nach so etwas wie dieses sind:

public static boolean pathExistsBidirectional(Node a, Node b) { 
    // BFS on both nodes at the same time 
    Queue<Node> queueA = new Queue<Node>(); 
    Queue<Node> queueB = new Queue<Node>(); 
    Set<Node> visitedA = new HashSet<Node>(); 
    Set<Node> visitedB = new HashSet<Node>(); 

    visitedA.add(a); 
    visitedB.add(b); 
    queueA.add(a); 
    queueB.add(b); 

    while (!queueA.isEmpty() && !queueB.isEmpty()) { 
     if (pathExistsBidirectionalHelper(queueA, visitedA, visitedB)) { 
     return true; 
     } 
     if (pathExistsBidirectionalHelper(queueB, visitedB, visitedA)) { 
     return true; 
     } 
    } 

    return false; 
    } 

    private static boolean pathExistsBidirectionalHelper(Queue<Node> queue, Set<Node> visitedFromThisSide, Set<Node> visitedFromThatSide) { 
    if (!queue.isEmpty()) { 
     Node next = queue.remove(); 
     for (Node adjacent : next.getAdjacent()) { 
     if (visitedFromThatSide.contains(adjacent)) { 
      return true; 
     } else if (visitedFromThisSide.add(adjacent)) { 
      queue.add(adjacent); 
     } 
     } 
    } 
    return false; 
    }