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