Bidirectional Search : Two-End BFS
Get started
জয় শ্রী রাম
🕉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
Consider following simple example-
0 11
\ /
4 9
/ \ / \
1 \ / 12
\ /
6 ---- 7 ---- 8
/ \
2 / \ 13
\ / \ /
5 10
/ \
3 14
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 O(b^d). On the other hand, if we execute two search operation then the complexity would be O(b^{d/2})
for each search and total complexity would be O(b^{d/2}+b^{d/2}) which is far less than O(b^d).
When to use bidirectional approach?
- 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(b^{d/2})
Algorithm:
Below is the pseudocode of the Bidirectional Search:
Image Source: http://planning.cs.uiuc.edu/node50.html
Implementation
Let’s see a naive C++ implementation of the bidirectional search using BFS:
// 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 << "\n";
cout << "Intersection at: " << intersectNode << "\n";
// print the path and exit the program
printPath(s_parent, t_parent, s, t, intersectNode);
exit(0);
}
}
return -1;
}
Now let’s have a look at the BFS() and isIntersecting() methods:
// 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;
};
Optimized Implementation
In this approach we basically do BFS from the source in forward direction and from the target in backward direction, alternatively, step-by-step. We don’t complete any of these two BFS wholly. Rather we incrementally approach towards each other from both direction and meet in at an intersection point (i.e, intersecting node) in the middle. This would become even clearer when you look the code shortly.
We take two queues: sourceQueue for BFS in forward direction from source to target and targetQueue which is used to do the BFS from the target towards the source in backward direction. We try to alternate between the two queues: sourceQueue and targetQueue; basically in every iteration we choose the smaller queue for the next iteration for the processing which effectively helps in alternating between the two queues only when the swapping between the two queues is profitable.
This helps in the following way:
As we go deeper into a graph the number of edges can grow exponentially. Since we are approaching in a balanced way, selecting the queue which has smaller number of nodes for the next iteration, we are avoiding processing a large number of edges and nodes by trying to having the intersection point somewhere in the middle.
Since we are processing both the target and source queue we are not going to much depth from any direction, either in forward direction (i.e, while processing source queue) or in backward direction (i.e, target queue which searches from target to source in backward manner).
Since we are starting BFS from source and target and meeting somewhere in the middle we are processing moderate number of nodes from each direction since we are not traversing the graph from starting point to all the way bottom to the leaf nodes (if we imagine the graph as tree for the time being) as we stop search in each direction somewhere in the middle which helps us avoiding exponentially increasing number of nodes towards the bottom (remember BFS searches all nodes in each level).
We will go into the implementation of this efficient approach by solving an interesting using this efficient Two-End BFS algorithm. Problem Statement:
Word Ladder: Given two words (beginWord and endWord), and a dictionary’s word list, find the length of shortest transformation sequence from beginWord to endWord, such that:
Only one letter can be changed at a time. Each transformed word must exist in the word list. Note that beginWord is not a transformed word.
For example,
Given:
beginWord = "cat"
endWord = "dog"
wordList = ["dat","dot","dog"]
As one shortest transformation is "cat" -> "dat" -> "dot" -> "dog", return its length 4.
Let’s use Java for this implementation.
Solution#1.
Login to Access Content
Another very similar implementation:
Login to Access Content
Yet another similar solution below. Pick the one you like the most:
Login to Access Content
