Explore Courses Blog Tutorials Interview Questions
0 votes
in AI and Deep Learning by (50.2k points)

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?

1 Answer

0 votes
by (108k points)

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:

Browse Categories