Implementation of the bidirectional graph search

Question

I am trying to implement a bi-directional graph search. As I understand, I should somehow merge two breadth-first searches, one which starts at the starting (or root) node and one which starts at the goal (or end) node. The bi-directional search terminates when both breadth-first searches "meet" at the same vertex.

Could you provide me with a code example(in Java, if possible) or link with the code for the bidirectional graph search?

Answer 1

Bidirectional search is a graph search algorithm that finds the smallest path from source to goal vertex. It runs two simultaneous search –

• Forward search form source/initial vertex toward goal vertex

• Backward search form goal/target vertex toward source vertex

Bidirectional search replaces a single search graph(which is likely to grow exponentially) with two smaller subgraphs – one starting from an initial vertex and another starting from goal vertex. The search terminates when two graphs intersect.

Here is a full implementation of Bidirectional search in java:

https://www.geeksforgeeks.org/bidirectional-search/