（c）广度优先搜索
看清 BFS 层序推进与队列操作，掌握无权图最短路径的求解逻辑与边界处理
按 空格/→ 演示下一步
全部页面点击任意一页，跳回舞台从这页播放
（c）广度优先搜索
看清 BFS 层序推进与队列操作，掌握无权图最短路径的求解逻辑与边界处理
化繁为简
走进迷宫想找出口,与其沿墙试探,不如从入口像水波一样一圈圈往外扩——先被淹到的一定是最近的点。这就是 BFS 的核心直觉。
波纹同一圈内的点距起点同样远,BFS 按层推进与此一致
策略
策略：定义、要点与典型应用
实现
策略想清楚了，落到代码其实就三件事：用对容器、做好标记、循环里按规矩取放。
第一圈完全扩散才到第二圈，队列 FIFO 正对应此顺序
可能情况
BFS 一层层往外走，但每处理一个节点都可能撞上不同局面——分清这几种情况，是写出正确实现的前提。
新房间标记去过的绕开找到出口就停全搜完仍没找到则目标不存在
实例
上一页我们写出了 BFS 的骨架——队列、FIFO、逐层推进。这一页反过来看：哪些问题该第一时间想到 BFS？
每扩散一圈 = 队列完成一层的标志，对应无权图最短路径
多连通
上页用一个完整实例跑通了 BFS，但那个图本身是一整块连通区域。现实中的图常常不止一块——地图上有被海洋隔开的多个岛屿，社交网络里有互不来往的几个小圈子。一个起点够不够？
每座孤岛都得从某点单独出发派船探，主岛探完不会自动跳到邻岛
复杂度
上一页我们一步步看 BFS 把图搜完。但要落地就躲不开一个问题——'这玩意儿要跑多久，占多大内存？'这一页，咱们把账彻底算清楚。
每经过一片水面 = V，每跨过一条水渠 = E，各自只发生一次
最短路径
你从家到公司，想找耗时最短的路线——是换乘最少，还是过路口最少？这种「边数最少」的问题，正是 BFS 的拿手好戏。
水波一圈圈同时外扩，最先抵达对岸的就是最短距离
本节要点
- ✓FIFO队列是BFS按层推进的内在节律
- ✓BFS天然解决无权图最短路问题
- ✓visited缺失会让BFS在带环图上崩溃
- ✓时空复杂度同为O(V+E)，与DFS同阶
- ✓入队-出队-扩展构成可迁移的通用骨架
课后思考
先独立想 5 分钟再对照参考答案。三问覆盖：核心机制、最短距离实现、图的全局遍历。
参考答案因为 BFS 按层推进：第一次到达即最短——任何绕远的路径都得跨更多层，步数只可能更多或相等。DFS 一路走到黑,撞到的第一条路径往往不是最短。
参考答案把 visited 数组升级成 distance:进入邻接点时执行 distance[neighbor] = distance[cur] + 1,每个顶点的最短距离就同步被记下。
参考答案可以。外层加循环:每次 BFS 跑完(队列空),若仍有未访问顶点,就从中再选一个起点继续。调用次数刚好等于连通块个数。