Skip to content

[pull] master from TheAlgorithms:master #122

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Merged
merged 1 commit into from
May 22, 2025
+201 −0
Merged

[pull] master from TheAlgorithms:master #122

Changes from all commits
Commits
Show all changes
1 commit
Select commit
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
201 changes: 201 additions & 0 deletions graphs/bidirectional_search.py
View file
Open in desktop
Original file line number Diff line number Diff line change
@@ -0,0 +1,201 @@
"""
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
"""

from collections import deque


def expand_search(
graph: dict[int, list[int]],
queue: deque[int],
parents: dict[int, int | None],
opposite_direction_parents: dict[int, int | None],
) -> int | None:
if not queue:
return None

current = queue.popleft()
for neighbor in graph[current]:
if neighbor in parents:
continue

parents[neighbor] = current
queue.append(neighbor)

# Check if this creates an intersection
if neighbor in opposite_direction_parents:
return neighbor

return None


def construct_path(current: int | None, parents: dict[int, int | None]) -> list[int]:
path: list[int] = []
while current is not None:
path.append(current)
current = parents[current]
return path


def 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
"""
if start == goal:
return [start]

# Check if start and goal are in the graph
if start not in graph or goal not in graph:
return None

# Initialize forward and backward search dictionaries
# Each maps a node to its parent in the search
forward_parents: dict[int, int | None] = {start: None}
backward_parents: dict[int, int | None] = {goal: None}

# Initialize forward and backward search queues
forward_queue = deque([start])
backward_queue = deque([goal])

# Intersection node (where the two searches meet)
intersection = None

# Continue until both queues are empty or an intersection is found
while forward_queue and backward_queue and intersection is None:
# Expand forward search
intersection = expand_search(
graph=graph,
queue=forward_queue,
parents=forward_parents,
opposite_direction_parents=backward_parents,
)

# If no intersection found, expand backward search
if intersection is not None:
break

intersection = expand_search(
graph=graph,
queue=backward_queue,
parents=backward_parents,
opposite_direction_parents=forward_parents,
)

# If no intersection found, there's no path
if intersection is None:
return None

# Construct path from start to intersection
forward_path: list[int] = construct_path(
current=intersection, parents=forward_parents
)
forward_path.reverse()

# Construct path from intersection to goal
backward_path: list[int] = construct_path(
current=backward_parents[intersection], parents=backward_parents
)

# Return the complete path
return forward_path + backward_path


def main() -> None:
"""
Run example of bidirectional search algorithm.

Examples:
>>> main() # doctest: +NORMALIZE_WHITESPACE
Path from 0 to 11: [0, 1, 3, 7, 11]
Path from 5 to 5: [5]
Path from 0 to 3: None
"""
# Example graph represented as an adjacency list
example_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],
}

# Test case 1: Path exists
start, goal = 0, 11
path = bidirectional_search(graph=example_graph, start=start, goal=goal)
print(f"Path from {start} to {goal}: {path}")

# Test case 2: Start and goal are the same
start, goal = 5, 5
path = bidirectional_search(graph=example_graph, start=start, goal=goal)
print(f"Path from {start} to {goal}: {path}")

# Test case 3: No path exists (disconnected graph)
disconnected_graph = {
0: [1, 2],
1: [0],
2: [0],
3: [4],
4: [3],
}
start, goal = 0, 3
path = bidirectional_search(graph=disconnected_graph, start=start, goal=goal)
print(f"Path from {start} to {goal}: {path}")


if __name__ == "__main__":
main()