Bidirectional search facts for kids
In computer science, bidirectional search is a method used for finding the shortest path between two items in a graph. It runs two simultaneous searches starting from the two items.
Implementation
The example below uses two simultaneous breadth-first searches.
void bidirectionalSearch(Item a, Item b) {
Queue qA = new Queue();
Queue qB = new Queue();
qA.enqueue(a);
qB.enqueue(b);
while (!qA.isEmpty() && !qB.isEmpty()) {
if (!qA.isEmpty()) {
Item v = qA.dequeue();
if (aItem.found) return true;
for (Item neighbor : v.neighbors()) {
if (!neighbor.found) {
neighbor.found = true;
qA.enqueue(neighbor);
}
}
}
if (!qB.isEmpty()) {
Item v = qB.dequeue();
if (v.found) return true;
for (Item neighbor : v.neighbors()) {
if (!neighbor.found) {
neighbor.found = true;
qB.enqueue(neighbor);
}
}
}
}
return false;
}Related pages
All content from Kiddle encyclopedia articles (including the article images and facts) can be freely used under Attribution-ShareAlike license, unless stated otherwise. Cite this article:
Bidirectional search Facts for Kids. Kiddle Encyclopedia.