**故事的开始：迷宫题翻车现场** 我还记得第一次在面试中遇到图算法题的情景："给定一个迷宫，找到从入口到出口的最短路径。"我的大脑瞬间闪过所有看过的迷宫电影——比如《闪灵》里的树篱迷宫，只不过这次多了一个滴答作响的时钟和一块白板。 我尝试了朴素的深度优先搜索（DFS），沿着走廊一路走到底，撞墙后再像迷路的老鼠一样回溯。几分钟过去了，面试官挑了挑眉，说了一句让我至今难忘的话："在无权图中，有一种更简单的方法，能保证找到最短路径。" 那一刻，就像在游戏里发现了隐藏捷径——你已经反复刷同一个关卡好几个小时，突然发现了一个传送管道。我意识到，自己一直忽略了广度优先搜索（BFS）背后的"为什么"。它不仅仅是一种遍历方式，更是一种保证：**第一次到达某个节点时，你走的边数一定是最少的。** 理解这一点后，我的挫败感瞬间变成了兴奋。从那以后，BFS成了我解决最短路径问题的首选工具。 **核心洞见：为什么BFS能保证最短路径？** 想象你把一颗石子丢进平静的池塘。涟漪会均匀地向外扩散——**距离落点k的所有点，一定比距离k+1的点先被触达。** BFS做的正是这件事，只不过它借助了一个队列： 1. 从源节点开始，标记为已访问。 2. 将源节点入队。 3. 当队列不为空时，弹出队首节点，遍历它的所有邻居。任何未访问的邻居一律入队，并标记为已访问。 因为节点严格按"被发现顺序"处理，BFS会先探索距离0的所有节点，再依次探索距离1、距离2……以此类推。**当第一次遇到目标节点时，我们就能确定已经走了最少的边数**——任何其他路径都要经过某个已在同层或更早层处理过的节点，那样只会更长或至少一样长。 这个过程优雅、直观，而且时间复杂度仅为O(V+E)。无论是社交网络的好友推荐、GPS导航的路径规划，还是网络路由协议，BFS都在幕后默默工作。下次再看到"最短路径"四个字，希望你能想起那个池塘涟漪，以及那个不起眼的队列。
热门跟贴