graphs.bidirectional_search

Bidirectional Search Algorithm.

This algorithm searches from both the source and target nodes simultaneously, meeting somewhere in the middle. This approach can significantly reduce the search space compared to a traditional one-directional search.

Time Complexity: O(b^(d/2)) where b is the branching factor and d is the depth Space Complexity: O(b^(d/2))

https://en.wikipedia.org/wiki/Bidirectional_search

Functions

bidirectional_search(→ list[int] | None)	Perform bidirectional search on a graph to find the shortest path.
construct_path(→ list[int])
expand_search(→ int | None)
main(→ None)	Run example of bidirectional search algorithm.

Module Contents

graphs.bidirectional_search.bidirectional_search(graph: dict[int, list[int]], start: int, goal: int) → list[int] | None

Perform bidirectional search on a graph to find the shortest path.

Args:

graph: A dictionary where keys are nodes and values are lists of adjacent nodes start: The starting node goal: The target node

Returns:

A list representing the path from start to goal, or None if no path exists

Examples:

>>> graph = {
...     0: [1, 2],
...     1: [0, 3, 4],
...     2: [0, 5, 6],
...     3: [1, 7],
...     4: [1, 8],
...     5: [2, 9],
...     6: [2, 10],
...     7: [3, 11],
...     8: [4, 11],
...     9: [5, 11],
...     10: [6, 11],
...     11: [7, 8, 9, 10],
... }
>>> bidirectional_search(graph=graph, start=0, goal=11)
[0, 1, 3, 7, 11]
>>> bidirectional_search(graph=graph, start=5, goal=5)
[5]
>>> disconnected_graph = {
...     0: [1, 2],
...     1: [0],
...     2: [0],
...     3: [4],
...     4: [3],
... }
>>> bidirectional_search(graph=disconnected_graph, start=0, goal=3) is None
True

graphs.bidirectional_search.construct_path(current: int | None, parents: dict[int, int | None]) → list[int]

graphs.bidirectional_search.expand_search(graph: dict[int, list[int]], queue: collections.deque[int], parents: dict[int, int | None], opposite_direction_parents: dict[int, int | None]) → int | None

graphs.bidirectional_search.main() → None

Run example of bidirectional search algorithm.

Examples:

>>> main()
Path from 0 to 11: [0, 1, 3, 7, 11]
Path from 5 to 5: [5]
Path from 0 to 3: None