Bidirectional Searching Graph Algorithm

Bidirectional Search

We know our traditional searching algorithms to search for a goal vertex starting from a source
vertex  using BFS.In normal graph search using BFS/DFS we begin our search in one direction usually from source vertex toward the goal vertex, but what if we start search form both direction simultaneously.

So , Bidirectional search is a graph searching algorithm which find shortest path from source to goal vertex. It runs two simultaneous search that is.

1)Forward search form source/initial vertex toward goal vertex
2)Backward search form goal/target vertex toward source vertex

Bidirectional search replaces single search graph which is likely to grow exponentially with two smaller sub graphs – one starting from initial vertex and other starting from goal vertex. The search terminates when two graphs reach at same point or intersect each-other.

For Example:

Suppose we want to find if there exists a path from vertex 0 to vertex 14. Here we can execute two searches, one from vertex 0 and other from vertex 14. When both forward and backward search meet at vertex 7, we know that we have found a path from node 0 to 14 and search can be terminated now. We can clearly see that we have successfully avoided unnecessary exploration.


Now Question is why bidirectional approach?

Ans: Because

1)in many cases it is faster.

2)It dramatically reduce the amount of required exploration.

Let us suppose,

 if branching factor of tree is a and distance of goal vertex from source is d,
 then the normal BFS/DFS searching complexity would be O(a^d).

On the other hand, if we execute two search operation then the complexity would be O(a^{d/2})
for each search and total complexity would be O(a^{d/2}+a^{d/2}) which is far less than O(a^d).

When to use bidirectional approach?

1)Both initial and goal states are unique and completely defined.
The branching factor is exactly the same in both directions.

Performance measures

Completeness : Bidirectional search is complete if BFS is used in both searches.

Optimality : It is optimal if BFS is used for search and paths have uniform cost.
Time and Space Complexity : Time and space complexity is O(a^{d/2})

Sample Code:

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

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