提到“城市路径问题”很多自学算法的朋友第一时间想到的就是广度优先搜索BFS——比如你站在地铁站里想知道从A站到F站最少换乘几次或者从老城区到新城区最少经过多少个路口。地图App给出的“最少换乘”方案背后核心就是BFS。这篇博客我准备围绕城市路径问题把广度优先搜索算法从原理到代码、从“能跑”到“好用”完整拆一遍先讲怎么把城市路网变成程序能理解的图再给BFS的完整实现和路径回溯方案接着整理我在实际写这类代码时踩过的坑最后聊聊BFS的边界和优化思路。适合刚学完树和队列、想在真实场景里用BFS的读者也适合面试前突击算法题的同学。1. 把城市路网变成一张图BFS解决的问题到底是什么1.1 从“最少换乘”切入理解抽象的图模型先想一个问题地铁图从A站到F站怎么判断最少换乘几次很多人的第一反应是“打开地图看看”但程序不会看地图程序只能处理数据。要把城市路径问题交给计算机第一步是把路网抽象成图。一个图由节点和边组成。在地铁场景里每个站点是一个节点相邻站点之间的直达关系是一条边。注意这里的“边”不是地理上的公里数而是“乘坐一条线路能不能直接到达”。比如一号线从A站到B站中间没有其他站那A和B之间就有一条边如果A站和C站中间隔了一个站它们之间就没有直接的边。这样建出来的图叫无权图因为每条边的通行代价统一记为1次乘车不区分A到B是2公里还是10公里。为什么要把距离信息丢掉因为你要回答的问题是“最少换乘几次”而不是“最短里程是多少公里”。这两种目标对应完全不同的算法。最少换乘只看“经过多少条边”每条边都算一步最短里程要看每步的长短需要给边加权重。很多新手把这两个问题混在一起后面会发现BFS在某些场景下算出的并不是距离最短路线这个后面详细说。我经常用“朋友的朋友”来类比BFS的行为。你想认识一个陌生人最少通过几层朋友关系才能联系上你直接认识的朋友算第一层朋友的朋友算第二层朋友的朋友的朋友算第三层。BFS做的就是这件事先把身边所有朋友问一遍问不到谁认识目标再向朋友的朋友打听一层一层往外扩。城市路径问题里的BFS就是把“朋友”换成“相邻站点”把“几层关系”换成“换乘几次”。1.2 为什么无权图最短路径非BFS莫属这里要解释BFS为什么能找到最少换乘方案也就是正确性问题。BFS按层扩展每一层代表“从起点出发经过固定步数能到达的所有节点”。第0层是起点自己第1层是起点坐一站能到的所有站点第2层是坐两站能到的所有站点依此类推。当我们第一次遇到目标站点时它所在的层数就是从起点出发所需的最少乘车次数。这个结论成立的核心前提是每条边的代价完全相同都是1。BFS把扩展过的节点当作“已经确定最短步数”的节点而因为所有边代价一样先被访问到的节点一定比后访问到的节点更短或相等。如果边权不同比如A到B是10公里、B到C是1公里那步数少不代表里程短这时候用BFS就可能给出错误的“最短路径”得换Dijkstra算法。还有一个容易被忽略的点BFS天然具备“全局无死角”的特性。它不会像DFS那样沿着一条路走到底再回头而是同步扩展所有方向。这意味着只要目标可达BFS一定能找到路径不会因为方向选择问题而漏掉。对于城市路径这种需要保证“只要存在路线程序就必须给出答案”的场景这个特性非常重要。2. BFS的底层逻辑与完整实现2.1 队列、访问标记、前置节点BFS的三个核心要素先把BFS用到的数据结构摆出来理解它们为什么存在。第一个是队列。队列的特点是先进先出好比食堂打饭排队先来的人先打饭走人。BFS需要保证“先发现的节点先扩展”这样才能一层一层向外推进。如果用栈的话就会变成深度优先搜索最后走进一条岔路不回头。所以队列是BFS的骨架。第二个是访问标记集合visited。城市路网几乎一定有环地铁线路本身是闭合的换乘站会把多条线连接成复杂的网状结构。没有访问标记程序就会在一个环里反复转圈比如A到B、B到C、C又回到A永远停不下来。访问标记的作用是告诉程序“这个节点我已经处理过了别再来了”。第三个是前置节点记录predecessor。如果只想知道“能不能从A站到F站”BFS跑完就能回答。但现实中我们需要的是完整路径比如“A站坐1站到B站换乘二号线坐2站到D站再换乘三号线到F站”。前置节点数组记录“每个节点是从哪个节点走过来的”等BFS结束时从目标节点往前倒推就能还原整条路径。这三个要素缺一不可队列管顺序visited管收敛predecessor管结果。我在给项目做技术选型的时候经常跟团队强调不要只背BFS模板要理解每个变量存在的意义。面试时你把这三个点讲清楚比默写十遍代码更能体现水平。2.2 城市路网的代码建模邻接表这样建假设现在要处理一个小型城市的地铁网络包含6个站点和若干条线路每条线路是双向的。程序里最常用的图表示方式是邻接表。邻接表的核心思想是为每一个站点维护一个列表列表里存它直接相连的站点。用Python的字典来实现非常直观graph { A站: [B站, C站], B站: [A站, D站], C站: [A站, D站, E站], D站: [B站, C站, F站], E站: [C站, F站], F站: [D站, E站] }这样表示的意思是从A站出发可以直接到达B站和C站B站又连回A站和D站。实际构建邻接表时最常见的数据来源是“线路表”。比如一号线经过A、B、C、D四个站那么线路表中记录的是有序列表[A站, B站, C站, D站]。把这条线路变成邻接表需要遍历列表中的每个站点把它和前后相邻的站点互相建立连接。需要注意地铁线路通常是双向的所以A要连向BB也要连向A。def build_adjacency_list(lines): graph {} for line in lines: for i in range(len(line) - 1): station_a line[i] station_b line[i 1] if station_a not in graph: graph[station_a] [] if station_b not in graph: graph[station_b] [] graph[station_a].append(station_b) graph[station_b].append(station_a) return graph这段代码逻辑简单但有一个容易踩坑的地方如果两条线路在同一个换乘站相接邻接表只会记录“相邻站点”不会自动记录“换乘关系”。比如一号线在D站停靠二号线也在D站停靠你从一号线某站上车到了D站下车换二号线在图的层面看你其实是在D站节点上继续走二号线的邻接边。这个模型天然支持换乘不需要额外处理。换乘次数在BFS中体现为“路径经过了几个节点”从步数换算过来即可。2.3 从起点到终点BFS主流程的代码实现有了图之后就可以写BFS主流程了。下面这段代码实现了从指定起点出发搜索目标站点并返回是否可达。from collections import deque def bfs_can_reach(graph, start, target): if start target: return True queue deque([start]) visited set([start]) while queue: node queue.popleft() for neighbor in graph.get(node, []): if neighbor not in visited: visited.add(neighbor) if neighbor target: return True queue.append(neighbor) return False这段代码的执行流程是这样的先把起点放入队列标记为已访问。然后循环取出队首节点遍历它的所有邻居。如果邻居是目标直接返回True。如果邻居没访问过就标记并加入队列。队列为空说明从起点出发能到达的节点都找遍了目标仍然没出现返回False。注意这里visited标记的处理时机。我在上面代码里是“邻居入队前标记”这是正确的做法。如果改成“节点出队时再标记”同一个节点可能被多个邻居重复放入队列造成重复计算严重时在大图上会拖慢程序甚至内存溢出。这个问题在后面“常见问题”部分还会展开。3. 从“能不能到”到“怎么走”记录路径的关键技巧3.1 前置节点数组让路径可回溯上面代码只回答了“能不能到”但城市路径问题真正要的是“怎么走”。要拿到完整路径必须引入前置节点数组。前置节点数组的设计思想是“倒推”。BFS在扩展过程中每发现一个之前没见过的节点就记下“它是从哪个节点来的”。当BFS到达目标节点时从目标节点开始反复往前找前置节点直到回到起点再把顺序反过来就是完整路径。这个思路很像查族谱你从自己这一代往上找父亲、祖父、曾祖父一路找到祖先再把链条倒过来念一遍就是你的家族继承路径。用代码实现如下def reconstruct_path(predecessor, start, target): path [] node target while node is not None: path.append(node) node predecessor[node] path.reverse() return path前提是predecessor[start]要设置成None表示起点没有前置节点搜索到这里就停止了。3.2 完整代码改造输出“站到站”的换乘方案把上一节的predecessor整合进BFS做一个能返回完整路径的版本。from collections import deque def bfs_shortest_path(graph, start, target): if start target: return [start] queue deque([start]) visited set([start]) predecessor {start: None} while queue: node queue.popleft() for neighbor in graph.get(node, []): if neighbor not in visited: visited.add(neighbor) predecessor[neighbor] node if neighbor target: return reconstruct_path(predecessor, start, target) queue.append(neighbor) return None def reconstruct_path(predecessor, start, target): path [] node target while node is not None: path.append(node) node predecessor[node] path.reverse() return path用前面给出的6站点邻接表测试从A站到F站程序返回的路径是[A站, C站, D站, F站]这条路径的含义是从A站坐到C站从C站坐到D站从D站坐到F站一共坐了3站。换乘次数怎么算路径中有4个站点从起点到终点经过了3条边也就是3次乘车换乘次数等于乘车次数减1即2次。但严格说如果你只坐同一线路3站不需要换乘。这里的“换乘次数”在不同语境定义不同。最稳妥的做法是结合真实线路信息统计路径中相邻站点属于哪条线路线路切换的次数就是换乘次数。这需要在邻接表中额外记录“边属于哪条线”属于进阶改造后面讲。3.3 算法复杂度分析BFS为什么高效BFS的时间复杂度是O(VE)V是节点数E是边数。为什么是这个数因为每个节点最多入队一次、出队一次访问节点总耗时O(V)遍历每个节点的邻接表时每条边最多被检查两次双向图总耗时O(E)。对于城市路网这样的稀疏图边数通常和节点数成正比所以BFS实际跑起来非常快几万个站点的网络也能在毫秒级给出答案。空间复杂度是O(V)主要消耗在三个地方队列最多装下同一层的所有节点最坏情况下节点总数visited集合和predecessor字典也都是O(V)。对现代计算机来说几万个节点的城市路网占用空间完全可以忽略。真正导致内存问题的是构建邻接表时不小心把边重复添加这在第4部分会讲到。4. 实战中的常见问题与排查实录4.1 死循环与访问标记遗漏我在带项目时经常看到初学者写出卡死的BFS十次有八次是访问标记的问题。最常见的错误是在节点出队时才把它加入visited# 错误的写法 while queue: node queue.popleft() if node in visited: continue visited.add(node) for neighbor in graph[node]: queue.append(neighbor)这种写法在无环图里表现正常但在有环的城市路网里同一节点可能被多个邻居重复入队。比如A的邻居是B和CB和C的邻居又都是DD就会在B、C出队时被加入两次甚至更多次。图稍微复杂一点队列里全是重复节点不仅效率降低极端情况下内存也会被打爆。正确的做法是在节点入队之前就检查visited并标记保证一个节点只入队一次。也就是我在第2.3节代码里的写法。排查技巧也分享一下如果程序跑很久没结果先在代码里加一个计数器统计入队次数。入队次数明显大于节点总数基本可以断定是重复入队。此时优先检查visited标记的位置。4.2 内存膨胀与邻接表构建的坑第二个高频问题出在构建邻接表的时候。第一个坑是单向边。有些同学直接用线路列表只把前一个站连向后一个站忽略了双向。比如线路表是[A站, B站]只写了graph[A站].append(B站)没写graph[B站].append(A站)。结果BFS从A出发永远到不了B的下一站因为B站没有邻居。排查方法很简单打印邻接表看每个节点的邻居数是否合理。第二个坑是重复添加边。如果有两条线路共享同一个相邻段比如一号线和二号线都经过D站和E站且这两个站相邻那么构建时D到E的边会被添加两次。BFS本身不介意重复边只要visited标记正确多几条重复边只是多几次无效检查。但如果重复添加次数很多邻接表会变得很臃肿内存和耗时都会上升。建议在构建时先检查是否已存在或者最后对每个节点的邻居列表去重。我给某团队做过一次代码评审他们的城市数据有几十万条公交记录构建邻接表时没有去重内存直接飙到几个G程序秒崩。后来改成set去重内存降了一个数量级。这个优化非常值得做。4.3 场景变体从地铁最少换乘到公交步行组合城市路径问题不只有地铁一种场景。假设你要结合公交和步行BFS还能用吗答案是可以用但要小心建模。如果你把“每走一步路”和“每坐一站公交”都当作代价为1的边BFS可以算出最少步数但这个结果可能不符合直觉。例如你从小区门口走到公交站算1步公交坐10站算10步方案“走2步公交10站”的总步数是12可能比“走5步公交5站”的10步更差但实际通勤中人们更看重总时间或总距离而不是步数。所以当场景变成“最短时间”或“最短距离”就不能再用普通BFS需要给边赋值权重改用Dijkstra算法或者对图做分层处理。我在很多项目里见过团队硬用BFS处理带权图调了好几天参数都调不对最后发现方向错了。BFS适合的是“所有选择代价相同”的场景比如最少换乘次数、最少红绿灯路口数这些场景天然符合无权图假设。如果想扩展BFS处理时间最优可以把“换乘”和“乘坐”拆成不同层层间边权不同但BFS本身不支持边权所以更实际的是直接切换算法。这一点必须想清楚。5. 经验之谈BFS的边界与失效场景5.1 带权图与最短距离BFS的边界在哪上一节提到了带权图问题这里再展开说明。很多面试题喜欢问“BFS能不能求最短路径”答案是在无权图中可以在带权图中不可以。举一个反例假设从起点S到终点T有两条路第一条经过3条边但每条边长度为100公里第二条经过4条边但每条边长度为1公里。BFS会认为经过3条边的方案更优因为它的步数少但真实距离是300公里对4公里明显第二条更优。这就是边权破坏BFS最短性的典型场景。所以记住这个判断标准只有所有边的代价相等BFS才能保证最短。如果题目给的是红绿灯次数、换乘次数、操作步骤数这类统一计数的指标BFS是首选如果给的是距离、时间、金钱这类连续变量老实改用Dijkstra。5.2 双向BFS城市规模变大时的优化手段当城市路网规模变大比如某个区域有几千个站点BFS从起点单向扩散到终点可能需要扩展很多无关节点。一个非常实用的优化是双向BFS。双向BFS的思路是同时从起点和终点分别做BFS各扩展一层当两个搜索方向相交时就找到了最短路径。它的优势在于把搜索范围从“一个大圆”变成“两个小圆”相交时两个圆半径之和就是路径长度实际扩展的节点数大幅减少。我在处理一个模拟城市路网的项目时单向BFS平均要扩展800多个节点才能找到路径双向BFS只需要扩展不到100个节点速度快了将近一个数量级。实现上需要维护两个queue、两个visited、两个predecessor每次选择节点数少的一侧扩展当发现当前节点出现在另一侧visited中时把两条路径拼接起来即可。但双向BFS有一个前提图的边必须是双向的或者至少反向也能走。地铁线路通常是双向的适用。如果是单向道路比如某些公交单行线双向BFS就需要谨慎处理反向搜索的合法性。5.3 几点实操心得BFS这块代码虽然短但真要在工程里用好有几个心得值得记录。第一不要假设数据是干净的。真实城市数据里经常有孤立站点、重复线路、缺失连接。BFS前先对邻接表做基础校验比如每个节点的邻居数是否合理、是否存在自环能省很多调试时间。第二predecessor字典在路径很长时可能占用不少内存。如果只需要最短步数而不需要完整路径可以去掉predecessor省下一块空间。反过来如果确实需要路径务必在记录路径时注意方向反转这是最容易出bug的位置。第三编号和名称的问题。城市站点可能有中文名、英文名、数字编号BFS完全不在乎节点是什么类型只要哈希一致、可比较就行。但如果用自定义对象作为节点记得实现好等价性和哈希函数否则visited集合会出现严重Bug。第四调试BFS最好用可视化。我写BFS时习惯把每个节点的层数打印出来或者在小图上用表格标注访问顺序这样能直观看到“扩展层”是否合理。等确认逻辑正确后再接入真实大数据不要在复杂图上直接调试。最后再分享一个小技巧BFS的队列初始化和visited标记要始终绑在一起。无论怎么变体只要发现某段代码里出现了“先入队后标记”或者“入队前不标记”多半就是性能瓶颈或死循环的源头。把“入队即标记”当成一条铁律能省去很多排查时间。