Appearance
26. 地铁线路图（图与 BFS）
知识点：图（graph）+ 广度优先搜索（BFS）—— 一圈一圈扩散，先到的就是最近（O(V+E)）
项目：地铁换乘——最少坐几站？
故事开场：周末去游乐园
周末，你要坐地铁去游乐园。妈妈递给你一张地铁线路图：
家
↙ ↘
公园 学校
↙ ↘ ↘
超市 游乐场 图书馆
↘
动物园"从家到游乐场，最少坐几站？"妈妈问。
你盯着图："家 → 公园 → 游乐场，2 站！比 家 → 学校 → 图书馆…… 不对， 图书馆也到不了游乐场。反正就是 2 站！"
"那从家到动物园呢？"妈妈又问。
"嗯……家 → 公园 → 游乐场 → 动物园，3 站？"你数了数，"还有别的路吗？ 家 → 学校 → …… 学校只能去图书馆，图书馆哪也去不了，死路。 所以是 3 站。"
你忽然意识到，你刚才做的事情，其实是个"算法"： 从家出发，先看 1 站能到哪，再看 2 站能到哪……一圈一圈往外扩。 第一个到达目标的圈数，就是最少的站数！
笨办法先行：DFS 乱走，绕远路
你决定把地铁图存进程序。每个站是一个节点，站与站之间的线路 是边——这种"节点 + 边"的结构，就是图（graph）。
存图最简单的方式，是邻接表：每个站，记一张"我能直达哪些站"的清单：
ts
// 地铁图：站点 → 能直达的站点列表（邻接表）
const metro = new Map<string, string[]>()
metro.set("家", ["公园", "学校"])
metro.set("公园", ["家", "超市", "游乐场"])
metro.set("学校", ["家", "图书馆"])
metro.set("超市", ["公园"])
metro.set("游乐场", ["公园", "动物园"])
metro.set("图书馆", ["学校"])
metro.set("动物园", ["游乐场"])然后你想起第 23 章的迷宫 DFS，顺手就写了个"递归乱走"：
ts
// 从 start 出发，DFS 乱走，看能不能到 target（顺便数步数）
let bestSteps = Infinity
function dfs(start: string, target: string, steps: number): void {
if (start === target) {
if (steps < bestSteps) {
bestSteps = steps // 记下目前最短的
}
return
}
const next = metro.get(start)
if (next === undefined) { return }
for (let i = 0; i < next.length; i++) {
dfs(next[i], target, steps + 1) // 每条路都试试
}
}
dfs("家", "动物园", 0)
console.log("最少 " + bestSteps + " 站")输出：
最少 3 站算对了！可你把图改大一点（100 个站、每站 4 条线），这个 DFS 就开始发疯——它把所有路都走了一遍，包括绕地球一圈的 "家 → 公园 → 家 → 公园 → 家……"这种原地转圈的蠢路！ 而且它不记得自己走过哪，转圈的次数没有上限。
"有没有更聪明的办法？"你想起第 19 章的层序遍历—— "一圈一圈走"，好像就是干这个的！
引出知识点：BFS——"一圈一圈"扩散
广度优先搜索（Breadth-First Search，简称 BFS），就是 "一圈一圈扩散"的搜索：
- 第一圈：起点 1 站能到的站（公园、学校）
- 第二圈：2 站能到的站（超市、游乐场、图书馆）
- 第三圈：3 站能到的站（动物园！）
第一个到达目标的圈，就是最短的路径——因为我们是按"距离 从近到远"一圈圈扩的，任何更近的路，早就被发现了！
BFS 的实现，用队列（第 7 章的老朋友！）：
- 起点入队（第 0 圈）
- 从队首取出一个站，把它的邻居们全部入队（下一圈）
- 每次入队时，记录"这是第几圈"（走了几站）
- 出队时发现目标 → 它就是最短的！
还需要一个"记过的人"清单（Set）：已经去过/排队中的站， 不再入队——不然又会原地转圈（家 → 公园 → 家 → 公园……）！
ts
const visited = new Set<string>() // 记过的人（去过的站）（Set 和 Map 是亲戚：Map 存"钥匙 → 值"，Set 只存"钥匙"本身。 visited.has("公园") 问"去过公园吗"，visited.add("公园") 记下"去过"。 还记得第 8 章吗？Map/Set 的查找都是 O(1)。）
动手实现：BFS 找最短站数
ts
// 地铁图：站点 → 能直达的站点列表
const metro = new Map<string, string[]>()
metro.set("家", ["公园", "学校"])
metro.set("公园", ["家", "超市", "游乐场"])
metro.set("学校", ["家", "图书馆"])
metro.set("超市", ["公园"])
metro.set("游乐场", ["公园", "动物园"])
metro.set("图书馆", ["学校"])
metro.set("动物园", ["游乐场"])
// BFS：从 start 到 target 最少几站？到不了返回 -1
function shortestStops(start: string, target: string): number {
const queue: string[] = [start] // 队列：待处理的站
const visited = new Set<string>([start]) // 记过的人
let stops = 0 // 目前是第几圈
while (queue.length > 0) {
const size = queue.length // 这一圈有多少个站
for (let i = 0; i < size; i++) {
const station = queue.shift() // 出队
if (station === undefined) { continue }
if (station === target) {
return stops // 这一圈找到目标！
}
const next = metro.get(station) // 它的邻居们
if (next !== undefined) {
for (let j = 0; j < next.length; j++) {
if (!visited.has(next[j])) { // 没去过？
visited.add(next[j]) // 记下来
queue.push(next[j]) // 排到下一圈
}
}
}
}
stops++ // 这一圈走完了，进入下一圈
}
return -1 // 所有站都走遍了，到不了
}
console.log("家 → 游乐场：" + shortestStops("家", "游乐场") + " 站")
console.log("家 → 动物园：" + shortestStops("家", "动物园") + " 站")
console.log("家 → 图书馆：" + shortestStops("家", "图书馆") + " 站")输出：
家 → 游乐场：2 站
家 → 动物园：3 站
家 → 图书馆：2 站全部正确！ 而且 BFS 保证找到的一定是最短的——不是碰运气。
（注意 size 变量：先数清"这一圈有几个站"，只处理它们； 处理完一圈 stops++，下一圈就是"再多坐一站"。这就是 "按圈扩散"的实现秘诀。）
跑起来：BFS vs DFS，谁先找到？
给 BFS 和 DFS 各加一个计数器，看看谁"走的步数"少：
ts
// BFS 版：数一数它一共访问了几个站
function shortestStopsCount(start: string, target: string): number {
const queue: string[] = [start]
const visited = new Set<string>([start])
let stops = 0
let visits = 1 // 计数器：访问过的站
while (queue.length > 0) {
const size = queue.length
for (let i = 0; i < size; i++) {
const station = queue.shift()
if (station === undefined) { continue }
if (station === target) {
console.log("BFS 访问了 " + visits + " 个站")
return stops
}
const next = metro.get(station)
if (next !== undefined) {
for (let j = 0; j < next.length; j++) {
if (!visited.has(next[j])) {
visited.add(next[j])
queue.push(next[j])
visits++
}
}
}
}
stops++
}
return -1
}
shortestStopsCount("家", "动物园")输出：
BFS 访问了 7 个站7 个站，BFS 全部访问到了——因为动物园在第 3 圈（第 3 站）， 而它前面还排着图书馆。注意：BFS 仍然保证 3 站是最短的—— 因为它把第 2 圈（超市、游乐场、图书馆）全部检查完才进入 第 3 圈，任何 2 站能到的路早就被发现了。目标越近，它越早收工。
图的世界
这一章，你正式进入了**图（graph）**的世界——计算机科学里 最庞大、最实用的数据结构：
- 社交网络：人是节点，朋友关系是边
- 地图导航：路口是节点，道路是边
- 网页：网页是节点，超链接是边
- 棋盘：格子是节点，一步能到的地方是边
BFS 在图上能解决无数问题：最少换乘、社交网络"几度人脉"、 游戏最短路线、迷宫最短路径（第 23 章的迷宫，用 BFS 也能解， 而且找到的就是最短的！）。
BFS 的复杂度：每个站入队一次（V 个节点），每条线被看一次 （E 条边）——总共 O(V + E)，图多大，它就走多久，不多不少。
小挑战
- 打印路径：改造
shortestStops，让它不仅能算"几站"， 还能打印走的具体路线（提示：每个站入队时，记下"我是从 哪个站来的"，找到目标后一路"倒着找爸爸"）。 - 最少换乘：把图改成"线路"视角——站之间如果不用换乘 就是同一条线。想一想：怎么表示，才能算"最少换乘几次"？ （提示：图里还可以加一种节点：把"线路"也当成节点！）
- 几度人脉：在社交网络图里，用 BFS 算"你到小明是几度人脉" （提示：一度 = 直接是朋友，二度 = 朋友的朋友……这就是 BFS 的"圈数"！）。
课后练习
第 1 题（动手题）：我家的地铁图
画一张你家附近的地铁图（至少 5 个站、1 条换乘线），存成邻接表， 用 shortestStops 算 3 对站点之间的最少站数，手动验证。
参考答案（点开查看）
示例（把站名换成你家的）：
ts
const metro = new Map<string, string[]>()
metro.set("家", ["医院", "学校"])
metro.set("医院", ["家", "商场"])
metro.set("学校", ["家", "公园"])
metro.set("商场", ["医院", "动物园"])
metro.set("公园", ["学校", "动物园"])
metro.set("动物园", ["商场", "公园"])
console.log(shortestStops("家", "动物园")) // 3
console.log(shortestStops("家", "商场")) // 2
console.log(shortestStops("医院", "公园")) // 3手动验证方法：在地图上沿着边数一数，对比程序输出。 如果程序给出的数字比手数的大，说明你漏画了一条边； 比手数的小，说明图画重了（或者程序有 bug——自己找找！）。
第 2 题（思考题）：BFS 为什么最短？
BFS 是按"圈数"扩散的（第 0 圈 = 起点，第 1 圈 = 1 站可达……）。 为什么"第一圈到达目标"就一定是"最少站数"？会不会有更短的 路藏在后面的圈里？
参考答案（点开查看）
不会。
BFS 严格按距离从近到远扩散：第 0 圈是最短距离 0 的站， 第 1 圈是最短距离 1 的站……第 k 圈是最短距离 k 的站。
如果存在一条 2 站就能到的路，那个目标一定在第 2 圈就被发现了； 到第 5 圈才找到目标，说明它到起点的最短距离就是 5—— 任何更短的路，都会在更早的圈里被碰到。
这就像水波一圈圈荡开：第一个碰到石头的波纹，一定是最近 的那一圈。 所以 BFS 找到的路径，一定是全局最短的。
第 3 题（思考题）：BFS vs DFS
BFS 用队列（先进先出），DFS 用递归/栈（后进先出）。想一想：
① 找"有没有路"（随便一条），用哪个都行？ ② 找"最短的路"，该用哪个？为什么？ ③ 数"一共有几条不同的路"，该用哪个？为什么？
参考答案（点开查看）
① 都行：只要连通性，两个都能找到（DFS 递归更简单好写）。 ② BFS：它一圈圈扩散，第一圈碰到就是最短；DFS 一条路走到黑， 找到的可能是绕远的路。 ③ DFS：它会把每条路都走到底（试遍所有可能性，像回溯！）； BFS 找到一条最短的就停了，不会去数"所有的路"。
一句话：要"最近/最短"→ BFS；要"全部/所有可能"→ DFS（回溯）。 迷宫找路两个都行，但 BFS 保证最短——下一章的"迷宫寻宝"， 我们试试 DFS 的另一面：把整个地图"逛遍"。
下一课预告：卫星图上的海洋里散落着几座小岛。老师说： "数一数有几座岛！"你从第一块陆地出发，一口气把整座岛 逛完、标记完，再找下一块没标记的陆地……这个"逛遍整座岛" 的办法，就是 DFS 的主场。