如何修改广度优先搜索(BFS)算法使其返回找到的路径长度

原代码核心问题 #

你的代码存在两个致命错误，导致无法正确统计路径长度：

• 初始化队列后未将起点"Start"加入队列，while q循环从一开始就不会执行
• 全局维护length变量、每出队一个节点就计数+1的逻辑完全不符合BFS层序遍历的特性：BFS会同时展开所有同距离的搜索分支，这种计数方式会统计所有遍历过的节点总数，根本无法对应起点到终点的单条路径长度

正确实现方式 #

BFS统计最短路径长度有两种通用写法，都能保证计数准确：

写法1：队列存储「节点+对应距离」（最直观，不易出错） #

直接在队列中存入元组，记录当前节点、以及起点到当前节点的路径长度，取出节点时如果是终点直接返回对应长度即可，邻接节点入队时长度在当前基础上+1。

from collections import deque

def bfs_path_length(graph, start, end):
    visited = set()
    q = deque()
    # 队列初始化：起点入队，起点到自身的边长度为0，若要统计节点数则初始值设为1
    q.append( (start, 0) )
    visited.add(start)

    while q:
        cur_node, cur_dist = q.popleft()
        # 命中终点直接返回当前距离
        if cur_node == end:
            return cur_dist
        # 邻接节点的距离为当前节点距离+1
        for neighbor in graph[cur_node]:
            if neighbor not in visited:
                visited.add(neighbor)
                q.append( (neighbor, cur_dist + 1) )
    # 无通路时返回约定值
    return 0

用你给出的示例图测试：

graph = { "Start" : ["A"],
          "A" : ["B"],
          "B" : ["End"],
          "End" : []
          }
print(bfs_path_length(graph, "Start", "End")) 
# 输出3，对应Start-A-B-End的3条边；如果初始长度设为1则输出4，对应路径上的4个节点

写法2：按层遍历统计长度 #

不需要在队列中存距离值，每次循环先拿到当前层的节点总数，处理完一整层所有节点后再给长度+1，同一层的所有节点到起点的距离完全一致。

from collections import deque

def bfs_path_length_by_layer(graph, start, end):
    visited = set()
    q = deque([start])
    visited.add(start)
    dist = 0

    while q:
        level_node_count = len(q)
        # 处理当前层所有节点
        for _ in range(level_node_count):
            cur_node = q.popleft()
            if cur_node == end:
                return dist
            for neighbor in graph[cur_node]:
                if neighbor not in visited:
                    visited.add(neighbor)
                    q.append(neighbor)
        # 当前层处理完毕，下一层节点的距离+1
        dist += 1
    return 0

注意：路径长度的统计规则可以按需调整，如果需要返回的是路径包含的节点总数，只需要把初始距离值设为1即可。

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