from collections import deque, defaultdict
def bidirectional_bfs(graph, start, end):
if start == end:
return [start]
# Initialize queues and visited dictionaries for both directions
q_start = deque([start])
q_end = deque([end])
visited_start = {start: None}
visited_end = {end: None}
while q_start or q_end:
# Search from start
if q_start:
path = bfs_step(graph, q_start, visited_start, visited_end)
if path:
return path
# Search from end
if q_end:
path = bfs_step(graph, q_end, visited_end, visited_start)
if path:
return path[::-1]
return None
def bfs_step(graph, queue, visited, other_visited):
current = queue.popleft()
for neighbor in graph[current]:
if neighbor not in visited:
visited[neighbor] = current
queue.append(neighbor)
if neighbor in other_visited:
# Meeting point found - reconstruct path
path = []
# Build path from start to meeting point
node = neighbor
while node is not None:
path.append(node)
node = visited[node]
path.reverse()
# Build path from meeting point to end
node = other_visited[neighbor]
while node is not None:
path.append(node)
node = other_visited[node]
return path
return None
# Build 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)
# Find shortest path from 0 to 6
path = bidirectional_bfs(graph, 0, 6)
print(f"Shortest path from 0 to 6: {path}")