Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags


How to use bidirectional search implementation in Python

Ethel Esenam Klu

A graph is a network of nodes connected by arcs or edges.

The two basic graph search algorithms, Breadth-First SearchBFS and Depth-First SearchDFS aim to find a path between 2 nodes (preferably the shortest) and determine cycles in the graph.

A graph search is done in one direction, either from the source/initial vertex to the goal/target vertex.

To search from both ends simultaneously, a bidirectional search is implemented.

Bidirectional search

Bidirectional search is a graph search algorithm that finds the shortest path from a source vertex to a goal vertex.

In implementing bidirectional search in Python, the graph search can either be:

  1. Forward search from the source to the goal vertex.
  2. Backward search from the goal to the source vertex.

The intersection of both forward and backward graphs indicates the end of the search, as displayed below.

Advantages and disadvantages of bidirectional search in Python

Advantage Disadvantage
1. Less time consuming as the shortest path length is used for the search. The goal node has to be known before the search can be done simultaneously in both directions.

When is it possible to use bidirectional search in Python?

The bidirectional approach can be used:

  1. When the branching factor for the forward and reverse direction is the same.
  2. When both the source and goal vertices are specified and distinct from each other.
Bidirectional search implementation in Python

Below is an implementation of bidirectional search in Python using BFS:

class adjacent_Node:
	def __init__(self, v):
		self.vertex = v = 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
	def AddEdge(self, source, last_node):
		node = adjacent_Node(last_node) = self.graph[source]
		self.graph[source] = node

		node = adjacent_Node(source) = self.graph[last_node]
		self.graph[last_node] = node
	def breadth_fs(self, direction = 'forward'):
		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_visited[vertex] = True
					self.source_parent[vertex] = current
				connected_node =
			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_visited[vertex] = True
					self.last_node_parent[vertex] = current
				connected_node =
	def is_intersecting(self):
		for i in range(self.vertices):
			if (self.source_visited[i] and
				return i
		return -1

	def path_st(self, intersecting_node,
				source, last_node):
		path = list()
		i = intersecting_node
		while i != source:
			i = self.source_parent[i]
		path = path[::-1]
		i = intersecting_node
		while i != last_node:
			i = self.last_node_parent[i]
		path = list(map(str, path))
		print(' '.join(path))
	def bidirectional_search(self, source, last_node):
		self.source_visited[source] = True
		self.source_parent[source] = -1
		self.last_node_visited[last_node] = True
		self.last_node_parent[last_node] = -1

		while self.source_queue and self.last_node_queue:
			self.breadth_fs(direction = 'forward')
			self.breadth_fs(direction = 'backward')
			intersecting_node = self.is_intersecting()
			if intersecting_node != -1:
				print("Path exists between {} and {}".format(source, last_node))
				print("Intersection at : {}".format(intersecting_node))
								source, last_node)
		return -1

if __name__ == '__main__':
	n = 17
	source = 1
	last_node = 16
	my_Graph = bidirectional_Search(n)
	my_Graph.AddEdge(1, 4)
	my_Graph.AddEdge(2, 4)
	my_Graph.AddEdge(3, 6)
	my_Graph.AddEdge(5, 6)
	my_Graph.AddEdge(4, 8)
	my_Graph.AddEdge(6, 8)
	my_Graph.AddEdge(8, 9)
	my_Graph.AddEdge(9, 10)
	my_Graph.AddEdge(10, 11)
	my_Graph.AddEdge(11, 13)
	my_Graph.AddEdge(11, 14)
	my_Graph.AddEdge(10, 12)
	my_Graph.AddEdge(12, 15)
	my_Graph.AddEdge(12, 16)
	out = my_Graph.bidirectional_search(source, last_node)
	if out == -1:
		print("No path between {} and {}".format(source, last_node))



View all Courses

Keep Exploring