我至今还记得第一次在面试中遇到图论题时的场景：“给定一个迷宫，找从入口到出口的最短路径。”我的大脑瞬间闪过所有看过的迷宫电影——《闪灵》里的树篱迷宫，只不过这次多了一个滴答作响的时钟和一块白板。我试着用朴素的深度优先搜索，一条走廊一条走廊地钻，碰到死胡同就原路返回，活像一只迷路的老鼠。痛苦地折腾了几分钟后，面试官挑了挑眉，说：“有一种更简单的方法，保证能在无权图中找到最短路径。” 那一刻的感觉，就像在游戏里发现了隐藏捷径——你明明在同一关卡里苦战了几个小时，突然看见一根水管能把你直接送到终点。我这才意识到，自己一直没弄懂广度优先搜索（BFS）背后的“为什么”。它不只是另一种遍历方式；它是一份保证：当你第一次到达某个节点时，走过的边数一定是最少的。理解了这一点，我的挫败感立刻变成了兴奋。从那以后，BFS就成了我解决最短路径问题的首选工具。 为什么BFS能在无权图中给出最短路径？想象你往平静的池塘里丢了一颗石子。涟漪以均匀的速度向外扩散——距离落点 k 处的每一点，一定比距离 k+1 处的每一点更早被触达。BFS做的就是这件事，而实现它的工具就是队列： ``` from collections import deque def bfs_shortest_path(graph, start, target): queue = deque([(start, 0)]) visited = {start} while queue: node, distance = queue.popleft() if node == target: return distance for neighbor in graph[node]: if neighbor not in visited: visited.add(neighbor) queue.append((neighbor, distance + 1)) return -1 # 目标不可达 ``` 因为队列遵循先进先出的顺序，我们总是先处理距离为 0 的节点，再处理距离为 1 的节点，接着是距离为 2 的节点，以此类推。当我们第一次遇到目标节点时，就可以确信已经走了最少的边数——任何其他路径都必须经过某个我们已经处理过的节点，而那条路径的长度只会更长或相等。 这个算法优美、直观，而且时间复杂度是线性的，与图的大小成正比。不需要花哨的优先队列，不需要启发式函数，只需要一个简单的队列和一个已访问集合。 回到开头那个迷宫题。用 BFS 重新审视时，解法变得异常简单：把迷宫的每个格子看作节点，格子之间的通道看作边。从入口开始做广度优先搜索，第一次到达出口的那一层深度，就是最短路径的长度。当年让我在面试官面前窘迫不堪的问题，如今成了我解释 BFS 威力时最爱的例子。很多时候，我们缺少的不是解决问题的能力，而是一个能看穿问题本质的视角。BFS 就是那个视角。
热门跟贴