Searching a graph is quite famous problem and have a lot of practical use. We have already discussed here how 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.**

Bidirectional search is a graph search algorithm which find smallest path form 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 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 intersect.**

Just like A* algorithm, bidirectional search can be guided by a heuristic estimate of remaining distance from source to goal and vice versa for finding shortest path possible.

Consider following simple 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.

**Why bidirectional approach?**

Because in many cases it is faster, it dramatically reduce the amount of required exploration.

Suppose if branching factor of tree is **b** and distance of goal vertex from source is **d**, then the normal BFS/DFS searching complexity would be . On the other hand, if we execute two search operation then the complexity would be for each search and total complexity would be which is far less than .

**When to use bidirectional approach?**

We can consider bidirectional approach when-

- 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

Below is very simple implementation representing the concept of bidirectional search using BFS. This implementation considers undirected paths without any weight.

`// C++ program for Bidirectional BFS search ` `// to check path between two vertices ` `#include <bits/stdc++.h> ` `using` `namespace` `std; ` ` ` `// class representing undirected graph ` `// using adjacency list ` `class` `Graph ` `{ ` ` ` `//number of nodes in graph ` ` ` `int` `V; ` ` ` ` ` `// Adjacency list ` ` ` `list<` `int` `> *adj; ` `public` `: ` ` ` `Graph(` `int` `V); ` ` ` `int` `isIntersecting(` `bool` `*s_visited, ` `bool` `*t_visited); ` ` ` `void` `addEdge(` `int` `u, ` `int` `v); ` ` ` `void` `printPath(` `int` `*s_parent, ` `int` `*t_parent, ` `int` `s, ` ` ` `int` `t, ` `int` `intersectNode); ` ` ` `void` `BFS(list<` `int` `> *queue, ` `bool` `*visited, ` `int` `*parent); ` ` ` `int` `biDirSearch(` `int` `s, ` `int` `t); ` `}; ` ` ` `Graph::Graph(` `int` `V) ` `{ ` ` ` `this` `->V = V; ` ` ` `adj = ` `new` `list<` `int` `>[V]; ` `}; ` ` ` `// Method for adding undirected edge ` `void` `Graph::addEdge(` `int` `u, ` `int` `v) ` `{ ` ` ` `this` `->adj[u].push_back(v); ` ` ` `this` `->adj[v].push_back(u); ` `}; ` ` ` `// Method for Breadth First Search ` `void` `Graph::BFS(list<` `int` `> *queue, ` `bool` `*visited, ` ` ` `int` `*parent) ` `{ ` ` ` `int` `current = queue->front(); ` ` ` `queue->pop_front(); ` ` ` `list<` `int` `>::iterator i; ` ` ` `for` `(i=adj[current].begin();i != adj[current].end();i++) ` ` ` `{ ` ` ` `// If adjacent vertex is not visited earlier ` ` ` `// mark it visited by assigning true value ` ` ` `if` `(!visited[*i]) ` ` ` `{ ` ` ` `// set current as parent of this vertex ` ` ` `parent[*i] = current; ` ` ` ` ` `// Mark this vertex visited ` ` ` `visited[*i] = ` `true` `; ` ` ` ` ` `// Push to the end of queue ` ` ` `queue->push_back(*i); ` ` ` `} ` ` ` `} ` `}; ` ` ` `// check for intersecting vertex ` `int` `Graph::isIntersecting(` `bool` `*s_visited, ` `bool` `*t_visited) ` `{ ` ` ` `int` `intersectNode = -1; ` ` ` `for` `(` `int` `i=0;i<V;i++) ` ` ` `{ ` ` ` `// if a vertex is visited by both front ` ` ` `// and back BFS search return that node ` ` ` `// else return -1 ` ` ` `if` `(s_visited[i] && t_visited[i]) ` ` ` `return` `i; ` ` ` `} ` ` ` `return` `-1; ` `}; ` ` ` `// Print the path from source to target ` `void` `Graph::printPath(` `int` `*s_parent, ` `int` `*t_parent, ` ` ` `int` `s, ` `int` `t, ` `int` `intersectNode) ` `{ ` ` ` `vector<` `int` `> path; ` ` ` `path.push_back(intersectNode); ` ` ` `int` `i = intersectNode; ` ` ` `while` `(i != s) ` ` ` `{ ` ` ` `path.push_back(s_parent[i]); ` ` ` `i = s_parent[i]; ` ` ` `} ` ` ` `reverse(path.begin(), path.end()); ` ` ` `i = intersectNode; ` ` ` `while` `(i != t) ` ` ` `{ ` ` ` `path.push_back(t_parent[i]); ` ` ` `i = t_parent[i]; ` ` ` `} ` ` ` ` ` `vector<` `int` `>::iterator it; ` ` ` `cout<<` ```
"*****Path*****
"
``` `; ` ` ` `for` `(it = path.begin();it != path.end();it++) ` ` ` `cout<<*it<<` `" "` `; ` ` ` `cout<<` ```
"
"
``` `; ` `}; ` ` ` `// Method for bidirectional searching ` `int` `Graph::biDirSearch(` `int` `s, ` `int` `t) ` `{ ` ` ` `// boolean array for BFS started from ` ` ` `// source and target(front and backward BFS) ` ` ` `// for keeping track on visited nodes ` ` ` `bool` `s_visited[V], t_visited[V]; ` ` ` ` ` `// Keep track on parents of nodes ` ` ` `// for front and backward search ` ` ` `int` `s_parent[V], t_parent[V]; ` ` ` ` ` `// queue for front and backward search ` ` ` `list<` `int` `> s_queue, t_queue; ` ` ` ` ` `int` `intersectNode = -1; ` ` ` ` ` `// necessary initialization ` ` ` `for` `(` `int` `i=0; i<V; i++) ` ` ` `{ ` ` ` `s_visited[i] = ` `false` `; ` ` ` `t_visited[i] = ` `false` `; ` ` ` `} ` ` ` ` ` `s_queue.push_back(s); ` ` ` `s_visited[s] = ` `true` `; ` ` ` ` ` `// parent of source is set to -1 ` ` ` `s_parent[s]=-1; ` ` ` ` ` `t_queue.push_back(t); ` ` ` `t_visited[t] = ` `true` `; ` ` ` ` ` `// parent of target is set to -1 ` ` ` `t_parent[t] = -1; ` ` ` ` ` `while` `(!s_queue.empty() && !t_queue.empty()) ` ` ` `{ ` ` ` `// Do BFS from source and target vertices ` ` ` `BFS(&s_queue, s_visited, s_parent); ` ` ` `BFS(&t_queue, t_visited, t_parent); ` ` ` ` ` `// check for intersecting vertex ` ` ` `intersectNode = isIntersecting(s_visited, t_visited); ` ` ` ` ` `// If intersecting vertex is found ` ` ` `// that means there exist a path ` ` ` `if` `(intersectNode != -1) ` ` ` `{ ` ` ` `cout << ` `"Path exist between "` `<< s << ` `" and "` ` ` `<< t << ` ```
"
"
``` `; ` ` ` `cout << ` `"Intersection at: "` `<< intersectNode << ` ```
"
"
``` `; ` ` ` ` ` `// print the path and exit the program ` ` ` `printPath(s_parent, t_parent, s, t, intersectNode); ` ` ` `exit` `(0); ` ` ` `} ` ` ` `} ` ` ` `return` `-1; ` `} ` ` ` `// Driver code ` `int` `main() ` `{ ` ` ` `// no of vertices in graph ` ` ` `int` `n=15; ` ` ` ` ` `// source vertex ` ` ` `int` `s=0; ` ` ` ` ` `// target vertex ` ` ` `int` `t=14; ` ` ` ` ` `// create a graph given in above diagram ` ` ` `Graph g(n); ` ` ` `g.addEdge(0, 4); ` ` ` `g.addEdge(1, 4); ` ` ` `g.addEdge(2, 5); ` ` ` `g.addEdge(3, 5); ` ` ` `g.addEdge(4, 6); ` ` ` `g.addEdge(5, 6); ` ` ` `g.addEdge(6, 7); ` ` ` `g.addEdge(7, 8); ` ` ` `g.addEdge(8, 9); ` ` ` `g.addEdge(8, 10); ` ` ` `g.addEdge(9, 11); ` ` ` `g.addEdge(9, 12); ` ` ` `g.addEdge(10, 13); ` ` ` `g.addEdge(10, 14); ` ` ` `if` `(g.biDirSearch(s, t) == -1) ` ` ` `cout << ` `"Path don't exist between "` ` ` `<< s << ` `" and "` `<< t << ` ```
"
"
``` `; ` ` ` ` ` `return` `0; ` `} ` |

Output:

Path exist between 0 and 14 Intersection at: 7 *****Path***** 0 4 6 7 8 10 14

**References**

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.

## leave a comment

## 0 Comments