请求提供Python实现Bidirectional Search的代码示例（附已实现BFS代码）

没问题，我来帮你实现双向搜索～ 你理解的核心思路完全正确：同时从起点和终点分别进行广度优先搜索（BFS），当两个搜索的路径在某个节点交汇时，就找到了连接起点和终点的最短路径，这时候就可以终止搜索啦。

下面是完整的实现代码，我还加了测试用例方便你验证：

def bidirectional_search(graph, start, goal):
    # 初始化两个方向的队列、已访问集合和父节点映射（用于路径回溯）
    start_queue = [start]
    end_queue = [goal]
    start_visited = {start: None}  # 记录起点方向每个节点的父节点
    end_visited = {goal: None}     # 记录终点方向每个节点的父节点

    while start_queue and end_queue:
        # 先扩展起点方向的BFS
        current_start = start_queue.pop(0)
        # 检查当前节点是否已经被终点方向的搜索访问过
        if current_start in end_visited:
            # 找到交汇点，拼接路径并返回
            return _reconstruct_path(current_start, start_visited, end_visited)
        
        # 遍历当前节点的邻居
        for neighbor in graph[current_start]:
            if neighbor not in start_visited:
                start_visited[neighbor] = current_start
                start_queue.append(neighbor)
        
        # 再扩展终点方向的BFS
        current_end = end_queue.pop(0)
        # 检查当前节点是否已经被起点方向的搜索访问过
        if current_end in start_visited:
            # 找到交汇点，拼接路径并返回
            return _reconstruct_path(current_end, start_visited, end_visited)
        
        # 遍历当前节点的邻居
        for neighbor in graph[current_end]:
            if neighbor not in end_visited:
                end_visited[neighbor] = current_end
                end_queue.append(neighbor)
    
    # 如果两个队列都空了还没找到交汇点，说明起点到终点没有路径
    return None

def _reconstruct_path(meet_node, start_visited, end_visited):
    # 回溯得到从起点到交汇点的路径
    path = []
    current = meet_node
    while current is not None:
        path.append(current)
        current = start_visited[current]
    # 反转路径，变成起点到交汇点的顺序
    path.reverse()
    
    # 回溯得到从交汇点到终点的路径（跳过交汇点本身，避免重复）
    current = end_visited[meet_node]
    while current is not None:
        path.append(current)
        current = end_visited[current]
    
    return path

# 测试用例：运行一下看看效果
if __name__ == "__main__":
    # 定义一个示例无向图
    sample_graph = {
        'A': ['B', 'C'],
        'B': ['A', 'D', 'E'],
        'C': ['A', 'F'],
        'D': ['B'],
        'E': ['B', 'F'],
        'F': ['C', 'E']
    }
    
    start_point = 'A'
    goal_point = 'F'
    search_result = bidirectional_search(sample_graph, start_point, goal_point)
    
    if search_result:
        print(f"找到的最短路径: {' -> '.join(search_result)}")
    else:
        print("起点到终点不存在可达路径")

代码关键点说明 #

• 我们维护了两个独立的BFS状态：一个从起点出发，一个从终点出发
• 每次扩展完一个方向的节点后，都会检查是否和另一个方向的已访问节点重叠，重叠时就触发路径拼接
• _reconstruct_path函数负责把两个方向的路径拼接成完整的起点到终点的路径
• 相比单向BFS，双向搜索的时间和空间复杂度都会更低，因为两个搜索的范围都是从各自端点向中间延伸，覆盖的节点数更少

内容的提问来源于stack exchange，提问作者AAT