企业官网建设流程全解析

LeetCode 815 Bus Routes 题解：图论建模与 BFS 最少换乘方案（Go 实现）

【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go

导读

本题（LeetCode 815. Bus Routes，公交路线）要求在一组环形行驶的公交线路中，求出从起点站 S 到终点站 T 最少需要乘坐的公交车数量，若无法到达则返回 -1。解决该题的核心思路是把「站台-公交」关系转化为图论问题：站台是顶点、公交线路是连接顶点的"染色边"，再用 BFS 逐层扩散求出最少换乘次数。本文结合 LeetCode-Go 仓库中 815. Bus Routes.go 的完整实现与 815. Bus Routes_test.go 的测试用例，逐行讲解建模过程、BFS 分层细节、复杂度分析以及边界情况，读完即可独立复现并理解该题的标准解法。

题目定义与示例

我们有一系列公交路线，每一条路线routes[i]上都有一辆公交车在上面循环行驶。例如routes[0] = [1, 5, 7]表示第 0 辆公交车会按照1 -> 5 -> 7 -> 1 -> 5 -> 7 -> ...的站点顺序无限循环行驶。

问题描述：我们从车站S出发（初始时不在公交车上），要去往车站T。期间仅可乘坐公交车，求最少需要乘坐的公交车数量，返回 -1 表示不可能到达终点车站。

题目给出的标准示例：

Input: routes = [[1, 2, 7], [3, 6, 7]] S = 1 T = 6 Output: 2 Explanation: The best strategy is take the first bus to the bus stop 7, then take the second bus to the bus stop 6.

即最优策略是：先乘坐第 0 辆公交车从站 1 到站 7，再换乘第 1 辆公交车从站 7 到站 6，共乘坐 2 辆公交车。

输入约束

原题给出的约束条件如下，实现时需要据此设计合理的算法复杂度：

• 1 <= routes.length <= 500：最多 500 条公交线路。
• 1 <= routes[i].length <= 500：每条线路最多包含 500 个站点。
• 0 <= routes[i][j] < 10^6：站点编号的取值范围，站点总数可高达百万级，因此不能用"以站点编号为下标的数组"直接开满。

问题建模：把换乘问题转化为图论问题

原文档中给出了明确的建模思路，这也是本题最关键的转化步骤：

这一题可以转换成图论的问题，将每个站台看成顶点，公交路径看成每个顶点的边。同一个公交的边染色相同。题目即可转化为从顶点 S 到顶点 T 需要经过最少多少条不同的染色边。

具体来说：

1. 顶点 = 公交站台。所有出现过的站台编号都是图中的顶点，顶点总数最多约500 × 500 = 250,000个（去重后）。
2. 边 = 公交线路。一辆公交车的线路会途经多个站台，把这条线路上经过的所有站台两两连通。同一个公交的所有边"染色"相同，代表同一辆公交车。
3. 换乘次数 = 经过的不同染色边的数量。从一个站台到另一个站台，每换乘一辆车就相当于切换一种"颜色"。题目要求的"最少乘坐的公交车数量"，等价于从顶点 S 到顶点 T 经过的最少不同染色边数。

由于边权（每换乘一辆车代价为 1）在分层意义上相等，这个问题天然适合用BFS（广度优先搜索）求解——BFS 天然保证首次到达某层时经过的边数最少。

这里有一个值得注意的建模细节：如果直接在"站台与站台"之间建边，一辆车有 k 个站台时会产生 O(k²) 条边，最坏情况下单条线路就有 25 万条边，空间难以承受。而仓库实现采用的建模方式是"站台 -> 公交"的映射：站台作为 BFS 队列中的扩展对象，公交作为"染色"的中间层，这样每条线路只被完整遍历一次，代价极小。

BFS 算法思路与数据结构设计

原文档给出的算法流程如下：

用 BFS 即可轻松解决。从起点 S 开始，不断的扩展它能到达的站点。用 visited 数组防止放入已经可达的站点引起的环。用 map 存储站点和公交车的映射关系（即某个站点可以由哪些公交车到达），BFS 的过程中可以用这个映射关系，拿到公交车的其他站点信息，从而扩张队列里面的可达站点。一旦扩展出现了终点 T，就可以返回结果了。

据此，算法需要三个核心数据结构：

BFS 的总体流程：

1. 若S == T，起点即终点，直接返回 0。
2. 预处理vertexMap：遍历所有路线，把"能到达站点 v 的公交车编号 i"追加到vertexMap[v]中。
3. 将起点站S入队，进入分层 BFS：每进入一层，乘坐的公交车数量res加 1。
4. 处理当前层的每个站台：通过vertexMap找到所有能到达该站的公交车；若某辆公交车已被乘坐（visited[bus] == true）则跳过；否则标记为已乘坐，并把该车线路上的所有站点入队；若其中恰好包含终点 T，立即返回当前的res。
5. 队列为空仍未到达 T，返回 -1。

Go 源码逐行讲解

仓库中的实现位于 leetcode/0815.Bus-Routes/815. Bus Routes.go，核心函数为numBusesToDestination。下面分段剖析其实现细节。

1. 特判起点等于终点

func numBusesToDestination(routes [][]int, S int, T int) int { if S == T { return 0 } ... }

当S == T时，不需要乘坐任何公交车即可到达，直接返回 0。这个特判必不可少——如果缺失，算法仍会返回 0 吗？不会：不特判的话，起点入队后第一层 BFS 就会把res加到 1 再检查站点，结果会错误地返回 1。仓库测试用例para815{[][]int{{1, 2, 7}, {3, 6, 7}}, 5, 5}, ans815{0}正是对这一分支的验证。

2. 构建站台到公交车的倒排索引

// vertexMap 中 key 是站点，value 是公交车数组，代表这些公交车路线可以到达此站点 vertexMap, visited, queue, res := map[int][]int{}, make([]bool, len(routes)), []int{}, 0 for i := 0; i < len(routes); i++ { for _, v := range routes[i] { tmp := vertexMap[v] tmp = append(tmp, i) vertexMap[v] = tmp } }

这一步遍历全部路线，为每个站台记录"有哪些公交车会停靠此站"。这是 BFS 中从"当前站台"快速获取"可乘坐的公交车"的跳板：

• visited的长度是len(routes)，与公交车数量一一对应，而不是与站点数量对应——这是本题的关键设计，因为 BFS 去重的对象是"公交车"而非"站台"。同一辆公交车的多个站点只需要扩展一次。
• vertexMap的 value 是公交车编号切片，存储的是"公交 -> 站点"关系的反向索引。

3. 分层 BFS 主循环

queue = append(queue, S) for len(queue) > 0 { res++ qlen := len(queue) for i := 0; i < qlen; i++ { vertex := queue[0] queue = queue[1:] for _, bus := range vertexMap[vertex] { if visited[bus] == true { continue } visited[bus] = true for _, v := range routes[bus] { if v == T { return res } queue = append(queue, v) } } } } return -1

这段代码是算法的核心，需要理解三个细节：

（1）分层计数：qlen := len(queue)与res++的配合。每次进入外层for循环先执行res++（表示"再乘坐一辆公交车"），然后固定当前层的队列长度qlen，只处理这qlen个站台。这样就能保证res严格等于"当前层站台对应的最少乘坐公交数"，即 BFS 的分层语义。如果在循环内直接以len(queue)作为结束条件而不先缓存qlen，新入队的下一层站点会被错误地当作本层处理，导致计数失真。

（2）以公交车为去重单位：visited[bus] == true。当站台vertex能由多辆公交车到达时，BFS 会逐一尝试这些车。若某辆车已经在更早的层被乘坐过，说明它的所有站点都已经或即将被扩展到，无需再次扩展，直接continue跳过。这一步同时承担了防环和剪枝的双重作用——公交路线是环形行驶的，如果不做该判断，BFS 会在同一辆车的站点之间无限循环。

（3）终点检查的时机。当扩展某辆公交车的线路站点v时，若发现v == T，立即返回res。注意此时的res已经包含了"乘坐当前这辆车"的计数，因此结果正确。由于 BFS 逐层推进，第一次遇到终点时返回的一定是最少乘坐数量。

最后，若队列耗尽仍未找到终点，说明从 S 出发可达的所有站台（即所有可乘坐的公交线路）都已被遍历，返回 -1。

复杂度分析

设公交线路数为 N（len(routes)），单条线路最大站点数为 K。

• 预处理阶段：遍历全部路线建立vertexMap，耗时 O(N × K)，最坏约 250,000 次操作。
• BFS 阶段：得益于visited数组，每辆公交车至多被扩展一次，每次扩展遍历其全部站点，因此总耗时同样为 O(N × K)。每个站点可能被多次入队（被不同公交车共享），但由于以公交为去重单位，整体开销仍受 N × K 上界约束，不会出现"每个站点 × 每辆车"的二次方爆炸。
• 空间复杂度：vertexMap存储了全部"站点 -> 公交"关系，最坏 O(N × K)；visited为 O(N)；队列最坏 O(N × K)。

综合来看，该实现在题目约束（N、K ≤ 500）下是线性可扩展的，远优于"站点两两建边"的 O(N × K²) 做法。

测试用例与运行验证

仓库为本题编写了完整的单元测试 leetcode/0815.Bus-Routes/815. Bus Routes_test.go，覆盖了三条关键路径：

测试代码遵循该仓库 LeetCode 题解的通用模式：定义para815/ans815结构体装载输入与期望答案，通过question815聚合后在Test_Problem815中循环比对，任一用例失败即调用t.Fatalf报告。运行验证方式如下：

# 进入题解所在目录执行测试（go.mod 模块名为 github.com/halfrost/LeetCode-Go） cd leetcode/0815.Bus-Routes && go test -v -run Test_Problem815

仓库根目录的 gotest.sh 脚本则用于对整个./leetcode/...目录生成统一的覆盖率文件：

go test -covermode=atomic -coverprofile=coverage.txt ./leetcode/...

这也印证了仓库"100% test coverage"的目标——每道题解都配有覆盖核心分支（含边界情况）的测试用例。

边界情况与易错点总结

1. S == T 必须特判返回 0，否则 BFS 第一轮就会把答案错算成 1（或陷入不必要的搜索）。
2. 去重对象是"公交车"而不是"站点"：visited数组长度应与len(routes)一致。公交路线环形行驶，同一辆车会被多次遇到，必须用visited[bus]拦截；若改成对站点去重，虽然也能工作，但会重复展开同一辆车的全部站点，且语义上不再贴合"乘坐了几辆车"的计数。
3. 分层 BFS 需先缓存qlen：res++每层只执行一次，内层循环严格限制在本层队列长度内，才能保证答案是最小换乘次数。
4. 终点检查放在"扩展站点"时：检查应在把站点入队之前完成，命中即返回当前res，避免多做一层无谓扩散。
5. 不可达情况的兜底：若起点 S 本身不在任何线路上，vertexMap[S]为空，第一层 BFS 无任何可扩展的公交车，队列很快耗尽，最终返回 -1，逻辑自然成立。
6. 站点编号范围大（< 10^6）：不能用定长数组以站点编号做下标，必须使用map做稀疏存储，这也是vertexMap选择map[int][]int的原因。

小结

LeetCode 815 是一道经典的"BFS + 图论建模"应用题：难点不在于 BFS 本身，而在于如何把"最少换乘公交"翻译成"最少染色边数"，以及选择"站台 -> 公交"的倒排索引作为扩展跳板。仓库 815. Bus Routes.go 的实现简洁清晰：一次预处理建立索引，一次分层 BFS 完成搜索，配合 815. Bus Routes_test.go 中换乘成功、起点终点相同、不可达三种用例，完整覆盖了题目所有关键分支，可直接作为同类"最少换乘/最少边数"问题的参考模板。

【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go