from collections import deque, defaultdict
def bidirectional_bfs(graph, start, end):
if start == end:
return [start]
# Initialize queues and visited sets for both directions
forward_queue = deque([start])
backward_queue = deque([end])
forward_visited = {start: None}
backward_visited = {end: None}
while forward_queue or backward_queue:
# Forward search
if forward_queue:
current = forward_queue.popleft()
for neighbor in graph[current]:
if neighbor in backward_visited:
# Found intersection - reconstruct path
return reconstruct_path(forward_visited, backward_visited, current, neighbor)
if neighbor not in forward_visited:
forward_visited[neighbor] = current
forward_queue.append(neighbor)
# Backward search
if backward_queue:
current = backward_queue.popleft()
for neighbor in graph[current]:
if neighbor in forward_visited:
# Found intersection - reconstruct path
return reconstruct_path(forward_visited, backward_visited, neighbor, current)
if neighbor not in backward_visited:
backward_visited[neighbor] = current
backward_queue.append(neighbor)
return None # No path found
def reconstruct_path(forward_visited, backward_visited, forward_node, backward_node):
# Build forward path
forward_path = []
current = forward_node
while current is not None:
forward_path.append(current)
current = forward_visited[current]
forward_path.reverse()
# Build backward path
backward_path = []
current = backward_node
while current is not None:
backward_path.append(current)
current = backward_visited[current]
# Combine paths
return forward_path + backward_path
# Create graph from edges
edges = [(0, 1), (0, 2), (1, 3), (3, 4), (4, 6), (2, 5), (5, 6)]
graph = defaultdict(list)
for u, v in edges:
graph[u].append(v)
graph[v].append(u) # Undirected graph
# Find shortest path between nodes 0 and 6
start_node = 0
end_node = 6
shortest_path = bidirectional_bfs(graph, start_node, end_node)
print(f"Shortest path from {start_node} to {end_node}: {shortest_path}")
print(f"Path length: {len(shortest_path) - 1}")