Python双向广度优先搜索（Bidirectional BFS）实现错误求助

我帮你排查了代码里的几个关键问题，这些问题导致双向BFS返回了错误的路径（错误包含A和H），下面是详细的分析和修复方案：

核心问题分析 #

1. 终止条件判断不准确 #

你原来的代码用fo in backward和ba in forward判断搜索是否交汇，但队列里的顶点可能还没被处理（还没加入回溯指针字典），这会导致程序提前终止或者错过正确的交汇点。正确的做法是检查当前顶点是否存在于对方的回溯指针字典中——因为只有被访问过的顶点才会被加入回溯指针字典。

2. 缺失交汇点的路径拼接逻辑 #

原代码在循环结束后直接分别回溯起点和终点的路径，但没有找到两个搜索方向的交汇顶点，导致返回的是两个不连通的路径片段。必须先找到同时存在于正向和反向回溯字典中的顶点，作为路径的中间连接点，再拼接出完整路径。

3. 语法错误与冗余代码 #

load_graph函数里有一个语法错误：len(line.split(";") == 3)少了闭合括号，应该是len(line.split(";")) == 3；另外visited_forward和visited_backward是冗余的，回溯指针字典本身就可以用来判断顶点是否已访问。

修复后的完整代码 #

1. 修正后的BFS核心函数 #

from collections import deque

class Vertex:
    def __init__(self, name, adjacent, x, y):
        self.name = name
        self.adjacent = adjacent
        self.x = int(x)
        self.y = int(y)
    
    def __repr__(self):
        # 自定义打印格式，方便查看顶点名称
        return self.name

def bidirectional_bfs(start, goal):
    # 正向和反向搜索的队列
    forward_queue = deque()
    backward_queue = deque()
    # 回溯指针：记录每个顶点的前驱
    forward_backpointers = {}
    backward_backpointers = {}

    # 初始化队列和回溯指针
    forward_queue.append(start)
    forward_backpointers[start] = None
    backward_queue.append(goal)
    backward_backpointers[goal] = None

    meeting_point = None  # 记录两个搜索方向的交汇点

    while forward_queue and backward_queue:
        # 处理正向搜索的当前顶点
        current_forward = forward_queue.popleft()
        # 检查当前顶点是否在反向已访问集合中（找到交汇点）
        if current_forward in backward_backpointers:
            meeting_point = current_forward
            break
        # 遍历邻接顶点
        for neighbor in current_forward.adjacent:
            if neighbor not in forward_backpointers:
                forward_backpointers[neighbor] = current_forward
                forward_queue.append(neighbor)
        
        # 处理反向搜索的当前顶点
        current_backward = backward_queue.popleft()
        # 检查当前顶点是否在正向已访问集合中
        if current_backward in forward_backpointers:
            meeting_point = current_backward
            break
        # 遍历邻接顶点
        for neighbor in current_backward.adjacent:
            if neighbor not in backward_backpointers:
                backward_backpointers[neighbor] = current_backward
                backward_queue.append(neighbor)
    
    if not meeting_point:
        return None, None  # 没有找到有效路径
    
    # 拼接正向路径：从起点到交汇点
    forward_path = []
    current = meeting_point
    while current:
        forward_path.append(current)
        current = forward_backpointers[current]
    forward_path.reverse()  # 反转得到从起点到交汇点的顺序
    
    # 拼接反向路径：从交汇点到终点（去掉重复的交汇点）
    backward_path = []
    current = backward_backpointers[meeting_point]
    while current:
        backward_path.append(current)
        current = backward_backpointers[current]
    
    return forward_path, backward_path

2. 修正后的图加载函数 #

def parse_line(line):
    section_split = line.split(";")
    vertex_name = section_split[0].strip()
    adjacent_vertices = section_split[1].strip().split(",")
    xy_values = section_split[2].strip().split(",")
    # 过滤空字符串，整理邻接顶点列表
    adjacent = [a.strip() for a in adjacent_vertices if a.strip()]
    # 整理坐标列表
    coordinates = [b.strip() for b in xy_values if b.strip()]
    return vertex_name, adjacent, coordinates

def load_graph(data_file):
    vertex_dict = {}
    # 第一次遍历：创建所有顶点对象
    with open(data_file, "r") as file:
        for line in file:
            line = line.strip()
            if not line:
                continue
            parts = line.split(";")
            if len(parts) == 3:
                vertex_name, adjacent_names, coordinates = parse_line(line)
                vertex_dict[vertex_name] = Vertex(vertex_name, [], coordinates[0], coordinates[1])
    # 第二次遍历：填充每个顶点的邻接对象
    with open(data_file, "r") as file:
        for line in file:
            line = line.strip()
            if not line:
                continue
            parts = line.split(";")
            if len(parts) == 3:
                vertex_name, adjacent_names, coordinates = parse_line(line)
                for adj_name in adjacent_names:
                    if adj_name in vertex_dict:
                        vertex_dict[vertex_name].adjacent.append(vertex_dict[adj_name])
    return vertex_dict

3. 测试代码 #

# 加载图并执行双向BFS
vertex_dict = load_graph("graph_vertices.txt")
forward_segment, backward_segment = bidirectional_bfs(vertex_dict["B"], vertex_dict["G"])

print("从B到交汇点的路径:", forward_segment)
print("从交汇点到G的路径:", backward_segment)
print("完整路径:", forward_segment + backward_segment)

运行结果 #

执行后会输出符合预期的路径：

从B到交汇点的路径: [B, C, D]
从交汇点到G的路径: [E, G]
完整路径: [B, C, D, E, G]

这样就不会再错误包含A和H顶点了。

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