Understanding The Bidirectional Search Algorithm In Python

In this blog post, we will delve into a very interesting topic in the realm of programming - Bidirectional Search Algorithm. This algorithm, as the name suggests, is a graph search algorithm that finds the smallest path from a start vertex to a target vertex in a directed or undirected graph.

Bidirectional Search Algorithm is unique because it runs two simultaneous searches: one from the start vertex and one from the target vertex. The bidirectional search can drastically reduce the required search time by meeting in the middle.

Let's see how you can implement this in Python:

from collections import deque

class Graph:
    def __init__(self, vertices):
        self.vertices = vertices
        self.graph = [[0 for _ in range(vertices)] for _ in range(vertices)]
 
    def add_edge(self, src, dest): 
        self.graph[src][dest] = 1
        self.graph[dest][src] = 1

    def BFS(self, queue, visited):
        element, prev_path_length = queue.popleft()
        neighbours = self.graph[element]
        for i in range(self.vertices):
            if (visited[i] == None) and (neighbours[i] == 1):
                queue.append((i, prev_path_length + 1))
                visited[i] = prev_path_length + 1
        return visited

    def bidirectional_search(self, src, target):
        src_queue = deque([(src, 0)])
        target_queue = deque([(target, 0)])

        src_visited = [None] * self.vertices
        target_visited = [None] * self.vertices

        src_visited[src] = 0
        target_visited[target] = 0

        while src_queue and target_queue:
            src_visited = self.BFS(src_queue, src_visited)
            target_visited = self.BFS(target_queue, target_visited)

            path_found_length = None
            for i in range(self.vertices):
                if src_visited[i] != None and target_visited[i] != None:
                    if path_found_length == None:
                        path_found_length = src_visited[i] + target_visited[i]
                    else:
                        path_found_length = min(path_found_length, src_visited[i] + target_visited[i])
            
            if path_found_length is not None:
                return path_found_length

        return -1

In the above Python code, we construct a directed/undirected graph with vertices using adjacency matrix. add_edge function is responsible for adding an edge between src and dest. The BFS (Breadth-First Search) function is a helper function for performing Breadth-First Search from a given queue and visited array. In the bidirectional_search function, we execute Breadth-First Search from the src and target simultaneously and stop when a common vertex is visited from both ends.

The bidirectional_search function returns the length of the smallest path from src to target. If there is no path between src and target, it returns -1.

The Bidirectional Search Algorithm is a faster search algorithm compared to BFS or DFS (Depth First Search). It is highly used for higher level searching where the tree is more deep. It allows for faster search times by decreasing the size of the search tree significantly.

This approach is particularly very suitable for vast search areas. However, it requires a lot more memory to store the nodes at each level, and hence might not be optimal for memory-restricted scenarios or very large datasets.

Happy Coding!

Note: This is just a simple implementation of the Bidirectional Search Algorithm. There are many other factors such as weight of a connection, data distribution etc that could influence the performance of search algorithms which are not considered in this example for simplicity.