# Bidirectional Search in Python

Also read: Depth First Iterative Deepening (DFID) Algorithm in Python

## What is Bidirectional Search?

A graph search algorithm called bidirectional search conducts two searches simultaneously. When the two searches meet at the midway, one stops moving forward from the starting point and the other stops moving backwards from the destination. For issues with a single start state and a single objective state, it is helpful.

When implementing a bidirectional search for k = 1, 2,…, the Depth First Iterative Deepening Search (DFID) can be used. In the kth iteration, instead of storing states but rather simply matching against the stored states generated from the forwarding direction, all states in the forward direction are generated from the start state up to depth k using breadth-first search and from the goal state up to depth k and depth k+ 1.

Here, to identify odd-length answers, a reverse or backward search to depth k+ 1 is required. If a match is identified, the route from the beginning to the matched state and from the matched state to the objective state can then be determined. It should be noted that each node has a link to its successors as well as to its parent. These links will help generate a complete path from start to goal states.

## How does Bidirectional Search work?

Let us illustrate the working of this method using an existing graph. Consider the following graph as shown in Figure. Consider the graph to find a route from the 1st node that is 1 to the last element 16.

Tracing nodes in both directions simultaneously.

## Implementing Bidirectional Search in Python

```class adjacent_Node:

def __init__(self, v):

self.vertex = v
self.next = None

class bidirectional_Search:

def __init__(self, vertices):

self.vertices = vertices
self.graph = [None] * self.vertices

self.source_queue = list()
self.last_node_queue = list()

self.source_visited = [False] * self.vertices
self.last_node_visited = [False] * self.vertices

self.source_parent = [None] * self.vertices
self.last_node_parent = [None] * self.vertices

node.next = self.graph[source]
self.graph[source] = node

node.next = self.graph[last_node]
self.graph[last_node] = node

if direction == 'forward':

current = self.source_queue.pop(0)
connected_node = self.graph[current]

while connected_node:
vertex = connected_node.vertex

if not self.source_visited[vertex]:
self.source_queue.append(vertex)
self.source_visited[vertex] = True
self.source_parent[vertex] = current

connected_node = connected_node.next
else:

current = self.last_node_queue.pop(0)
connected_node = self.graph[current]

while connected_node:
vertex = connected_node.vertex

if not self.last_node_visited[vertex]:
self.last_node_queue.append(vertex)
self.last_node_visited[vertex] = True
self.last_node_parent[vertex] = current

connected_node = connected_node.next

def is_intersecting(self):

#
for i in range(self.vertices):
if (self.source_visited[i] and
self.last_node_visited[i]):
return i

return -1

def path_st(self, intersecting_node,
source, last_node):

path = list()
path.append(intersecting_node)
i = intersecting_node

while i != source:
path.append(self.source_parent[i])
i = self.source_parent[i]

path = path[::-1]
i = intersecting_node

while i != last_node:
path.append(self.last_node_parent[i])
i = self.last_node_parent[i]

path = list(map(str, path))

print(' '.join(path))

def bidirectional_search(self, source, last_node):

self.source_queue.append(source)
self.source_visited[source] = True
self.source_parent[source] = -1

self.last_node_queue.append(last_node)
self.last_node_visited[last_node] = True
self.last_node_parent[last_node] = -1

while self.source_queue and self.last_node_queue:

intersecting_node = self.is_intersecting()

if intersecting_node != -1:
print("Path exists between {} and {}".format(source, last_node))
print("Intersection at : {}".format(intersecting_node))
self.path_st(intersecting_node,
source, last_node)
exit(0)
return -1

if __name__ == '__main__':

n = 17

source = 1

last_node = 16

my_Graph = bidirectional_Search(n)

out = my_Graph.bidirectional_search(source, last_node)

if out == -1:
print("No path between {} and {}".format(source, last_node))
```

OUTPUT:

Path exists between 1 and 16

Intersection at: 8

1 4 8 13 15 16

## Complexity of Bidirectional Search

The reason for this approach is that each of the two searches has a time complexity of O(b^d/2), and O(b^d/2+b^d/2) is much less than the running time of one search from the beginning to the goal, which would be O(b^d). This search can be made in an already existing graph/tree or a search graph/ tree can be generated as a part of the search.

• The speed with which we receive the desired results is one of the key advantages of bidirectional searches.
• By conducting multiple searches simultaneously, the search time is significantly shortened.
• Users can also conserve resources because less memory is necessary to store all of the searches.