关于公交路线

更高效的公交最少乘车次数规划：基于邻接矩阵 + 广度优先搜索的优化算法

摘要：日常公交出行规划中，“最少换乘（最少乘车次数）” 是用户最核心的需求之一。传统的全量遍历 BFS 算法在路线数量较多时效率偏低，本文基于 “邻接矩阵 + 哈希表预处理” 的思路，优化了公交路线间的换乘关系存储方式，结合广度优先搜索（BFS）实现了更高效的最少乘车次数计算。

一、为什么要优化？

之前我们组写过一个 “全量遍历” 的公交最少换乘算法，核心是每次搜索都遍历所有路线，判断能不能换乘。这个思路虽然好懂，但有个问题 ——路线多了就变慢。

比如一个城市有 100 条公交线，每次找换乘路线都要遍历 100 条，反复做 “检查两条路线有没有公共站点” 的操作，相当于做了大量重复计算。就像你查公交时，每找一次换乘都要把所有线路翻一遍，效率肯定高不了。

那能不能换个思路？提前把所有路线之间的换乘关系记下来，比如用一张 “路线换乘表”，想知道路线 A 和路线 B 能不能换乘，直接查表就行，不用每次都去比对站点。这就是本文算法的核心 —— 先预处理，再搜索，把 “重复劳动” 提前做完，让搜索过程更高效。

二、核心思路：先 “建表”，再 “搜路”

整个算法可以分成两大步：

预处理阶段：用哈希表记录 “每个站点对应哪些路线”，用邻接矩阵记录 “哪些路线之间可以换乘”—— 相当于提前建好两张关键的表；

BFS 搜索阶段：以 “路线” 为节点，利用建好的邻接矩阵，逐层搜索能到达终点的路线，找到最少乘车次数。

这个思路的本质是：用预处理的时间换搜索的时间，尤其适合需要多次查询的场景（比如同一个公交网络查不同起点终点）。

三、先搞懂几个关键 “工具”

在看代码之前，先把算法里用到的核心数据结构和概念说清楚，不然容易看懵。

3.1 哈希表（unordered_map）：快速找 “经过某站的所有路线”

哈希表的特点是 “键值对存储，查询速度快”，这里我们用它存：

键：站点编号（比如 1、5、7）；

值：经过这个站点的所有路线编号（比如经过站点 5 的路线有 0、2、3）。

举个例子，rec[5] = [0,2,3]，意思是 “站点 5 被路线 0、路线 2、路线 3 经过”。有了这个表，想知道 “哪些路线能到起点 S”，直接查rec[S]就行，不用遍历所有路线，这是第一个优化点。

3.2 邻接矩阵：快速判断 “两条路线能不能换乘”

邻接矩阵是一个二维数组edge，edge[i][j] = true表示 “路线 i 和路线 j 可以换乘”，false则表示不能。

比如有 3 条路线，邻接矩阵可能长这样：

意思是：路线 0 和 1 能换乘，路线 1 和 2 能换乘，路线 0 和 2 不能换乘。有了这个矩阵，判断两条路线能不能换乘，只需要查一下矩阵的值，不用再遍历站点比对，这是第二个优化点。

3.3 距离数组（dis）：记录 “坐几条线能到这条路线”

dis数组的下标是路线编号，值是 “从起点出发，最少坐几条线能到这条路线”。比如dis[2] = 3，意思是 “从起点到路线 2，最少需要坐 3 条公交线（换乘 2 次）”。

初始时dis数组全设为 - 1（表示没访问过），只有经过起点的路线，dis值设为 1（坐 1 条线就能到）。

四、代码逻辑拆解：一步步看懂

接下来我们把代码掰开揉碎，从预处理到搜索，每一步都讲清楚。

4.1 第一步：特殊情况处理 —— 起点就是终点

如果输入的起点 S 和终点 T 是同一个站，直接返回 0，不用查任何路线，这是最基础的优化。

if (S == T) {

return 0;}

4.2 第二步：预处理 1—— 构建哈希表和邻接矩阵

这是整个算法最核心的预处理步骤，目的是建好 “站点 - 路线” 表和 “路线 - 换乘” 表。

（1）初始化数据结构

int n = routes.size(); // 总路线数// 邻接矩阵：n行n列，初始全为false（不能换乘）

vector<vector<bool>> edge(n, vector<bool>(n, false));// 哈希表：键=站点，值=经过该站点的路线列表

unordered_map<int, vector<int>> rec;

（2）遍历所有路线，填充哈希表和邻接矩阵

for (int i = 0; i < n; i++) { // 遍历第i条路线

for (int stop : routes[i]) { // 遍历第i条路线的每个站点

// 关键：如果这个站点之前被其他路线经过过，说明这些路线和当前路线i能换乘

for (int j : rec[stop]) {

edge[i][j] = edge[j][i] = true; // 标记i和j可换乘（双向）

}

// 把当前路线i加入这个站点的路线列表

rec[stop].push_back(i);

}}

举个例子帮你理解：

先处理路线 0，站点是 [1,3,5]：

站点 1：rec 里没有，直接把路线 0 加入 rec [1]；

站点 3：rec 里没有，直接把路线 0 加入 rec [3]；

站点 5：rec 里没有，直接把路线 0 加入 rec [5]；

再处理路线 1，站点是 [5,7,9]：

站点 5：rec 里有路线 0，所以标记 edge [1][0] = edge [0][1] = true；然后把路线 1 加入 rec [5]；

站点 7：rec 里没有，加入 rec [7]；

站点 9：rec 里没有，加入 rec [9]。

这样一来，我们就知道路线 0 和 1 能换乘（因为都经过站点 5），邻接矩阵里对应的位置就变成了 true。

4.3 第三步：预处理 2—— 初始化 BFS 队列和距离数组

vector<int> dis(n, -1); // 距离数组，初始-1（未访问）

queue<int> que; // BFS队列，存路线编号

// 把所有经过起点S的路线加入队列，作为BFS的起点for (int bus : rec[S]) {

dis[bus] = 1; // 坐1条线就能到这条路线

que.push(bus);}

比如起点 S 是 1，rec [1] = [0]，那么 dis [0] = 1，队列里加入 0。

4.4 第四步：BFS 核心搜索 —— 找最少乘车次数

这一步的逻辑很简单：从经过起点的路线出发，逐层找能换乘的路线，记录每条路线的最少乘车次数。

while (!que.empty()) { // 队列不为空就继续

int x = que.front(); // 取出队首的路线x

que.pop(); // 弹出队首

for (int y = 0; y < n; y++) { // 遍历所有路线y

// 条件1：路线x和y能换乘；条件2：路线y没被访问过

if (edge[x][y] && dis[y] == -1) {

dis[y] = dis[x] + 1; // 乘车次数+1

que.push(y); // 把y加入队列，继续搜索

}

}}

还是举例子：

队列里初始是路线 0，dis [0]=1；

取出路线 0，遍历所有路线 y：

y=1：edge [0][1]=true，dis [1]=-1 → dis [1] = 1+1=2，加入队列；

其他路线：edge [0][y]=false，跳过；

接下来处理队列里的路线 1，继续找能换乘的路线……

4.5 第五步：计算最终结果 —— 找到达终点的最少乘车次数

int ret = INT_MAX; // 初始设为最大整数// 遍历所有经过终点T的路线for (int bus : rec[T]) {

if (dis[bus] != -1) { // 这条路线能到达

ret = min(ret, dis[bus]); // 取最小值

}}// 没找到就返回-1，否则返回最少乘车次数return ret == INT_MAX ? -1 : ret;

比如终点 T 是 9，rec [9] = [1]，dis [1]=2 → 最少乘车次数就是 2（换乘 1 次）。

4.6 辅助函数：手动输入路线和站点

这部分代码很简单，就是让用户输入路线数量、每条路线的站点数和站点编号，最终返回一个二维数组routes，比如routes = [[1,3,5],[5,7,9]]。

4.7 主函数：整合所有步骤

主函数的逻辑就是：

调用inputRoutes()让用户输入路线；

输入起点 S 和终点 T；

调用numBusesToDestination()计算最少乘车次数；

输出结果。

下面是全部代码：

更高效的公交最少乘车次数规划：基于邻接矩阵 + 广度优先搜索的优化算法

摘要：日常公交出行规划中，“最少换乘（最少乘车次数）” 是用户最核心的需求之一。传统的全量遍历 BFS 算法在路线数量较多时效率偏低，本文基于 “邻接矩阵 + 哈希表预处理” 的思路，优化了公交路线间的换乘关系存储方式，结合广度优先搜索（BFS）实现了更高效的最少乘车次数计算。

一、为什么要优化？聊聊传统算法的痛点

之前我们组写过一个 “全量遍历” 的公交最少换乘算法，核心是每次搜索都遍历所有路线，判断能不能换乘。这个思路虽然好懂，但有个致命问题 ——路线多了就变慢。

比如一个城市有 100 条公交线，每次找换乘路线都要遍历 100 条，反复做 “检查两条路线有没有公共站点” 的操作，相当于做了大量重复计算。就像你查公交时，每找一次换乘都要把所有线路翻一遍，效率肯定高不了。

那能不能换个思路？提前把所有路线之间的换乘关系记下来，比如用一张 “路线换乘表”，想知道路线 A 和路线 B 能不能换乘，直接查表就行，不用每次都去比对站点。这就是本文算法的核心 —— 先预处理，再搜索，把 “重复劳动” 提前做完，让搜索过程更高效。

二、核心思路：先 “建表”，再 “搜路”

整个算法可以分成两大步：

预处理阶段：用哈希表记录 “每个站点对应哪些路线”，用邻接矩阵记录 “哪些路线之间可以换乘”—— 相当于提前建好两张关键的表；

BFS 搜索阶段：以 “路线” 为节点，利用建好的邻接矩阵，逐层搜索能到达终点的路线，找到最少乘车次数。

这个思路的本质是：用预处理的时间换搜索的时间，尤其适合需要多次查询的场景（比如同一个公交网络查不同起点终点）。

三、先搞懂几个关键 “工具”

在看代码之前，先把算法里用到的核心数据结构和概念说清楚，不然容易看懵。

3.1 哈希表（unordered_map）：快速找 “经过某站的所有路线”

哈希表的特点是 “键值对存储，查询速度快”，这里我们用它存：

键：站点编号（比如 1、5、7）；

值：经过这个站点的所有路线编号（比如经过站点 5 的路线有 0、2、3）。

举个例子，rec[5] = [0,2,3]，意思是 “站点 5 被路线 0、路线 2、路线 3 经过”。有了这个表，想知道 “哪些路线能到起点 S”，直接查rec[S]就行，不用遍历所有路线，这是第一个优化点。

3.2 邻接矩阵：快速判断 “两条路线能不能换乘”

邻接矩阵是一个二维数组edge，edge[i][j] = true表示 “路线 i 和路线 j 可以换乘”，false则表示不能。

比如有 3 条路线，邻接矩阵可能长这样：

意思是：路线 0 和 1 能换乘，路线 1 和 2 能换乘，路线 0 和 2 不能换乘。有了这个矩阵，判断两条路线能不能换乘，只需要查一下矩阵的值，不用再遍历站点比对，这是第二个优化点。

3.3 距离数组（dis）：记录 “坐几条线能到这条路线”

dis数组的下标是路线编号，值是 “从起点出发，最少坐几条线能到这条路线”。比如dis[2] = 3，意思是 “从起点到路线 2，最少需要坐 3 条公交线（换乘 2 次）”。

初始时dis数组全设为 - 1（表示没访问过），只有经过起点的路线，dis值设为 1（坐 1 条线就能到）。

四、代码逻辑拆解：一步步看懂

接下来我们把代码掰开揉碎，从预处理到搜索，每一步都讲清楚。

4.1 第一步：特殊情况处理 —— 起点就是终点

如果输入的起点 S 和终点 T 是同一个站，直接返回 0，不用查任何路线，这是最基础的优化。

if (S == T) {

return 0;}

4.2 第二步：预处理 1—— 构建哈希表和邻接矩阵

这是整个算法最核心的预处理步骤，目的是建好 “站点 - 路线” 表和 “路线 - 换乘” 表。

（1）初始化数据结构

int n = routes.size(); // 总路线数// 邻接矩阵：n行n列，初始全为false（不能换乘）

vector<vector<bool>> edge(n, vector<bool>(n, false));// 哈希表：键=站点，值=经过该站点的路线列表

unordered_map<int, vector<int>> rec;

（2）遍历所有路线，填充哈希表和邻接矩阵

for (int i = 0; i < n; i++) { // 遍历第i条路线

for (int stop : routes[i]) { // 遍历第i条路线的每个站点

// 关键：如果这个站点之前被其他路线经过过，说明这些路线和当前路线i能换乘

for (int j : rec[stop]) {

edge[i][j] = edge[j][i] = true; // 标记i和j可换乘（双向）

}

// 把当前路线i加入这个站点的路线列表

rec[stop].push_back(i);

}}

举个例子帮你理解：

先处理路线 0，站点是 [1,3,5]：

站点 1：rec 里没有，直接把路线 0 加入 rec [1]；

站点 3：rec 里没有，直接把路线 0 加入 rec [3]；

站点 5：rec 里没有，直接把路线 0 加入 rec [5]；

再处理路线 1，站点是 [5,7,9]：

站点 5：rec 里有路线 0，所以标记 edge [1][0] = edge [0][1] = true；然后把路线 1 加入 rec [5]；

站点 7：rec 里没有，加入 rec [7]；

站点 9：rec 里没有，加入 rec [9]。

这样一来，我们就知道路线 0 和 1 能换乘（因为都经过站点 5），邻接矩阵里对应的位置就变成了 true。

4.3 第三步：预处理 2—— 初始化 BFS 队列和距离数组

vector<int> dis(n, -1); // 距离数组，初始-1（未访问）

queue<int> que; // BFS队列，存路线编号

// 把所有经过起点S的路线加入队列，作为BFS的起点for (int bus : rec[S]) {

dis[bus] = 1; // 坐1条线就能到这条路线

que.push(bus);}

比如起点 S 是 1，rec [1] = [0]，那么 dis [0] = 1，队列里加入 0。

4.4 第四步：BFS 核心搜索 —— 找最少乘车次数

这一步的逻辑很简单：从经过起点的路线出发，逐层找能换乘的路线，记录每条路线的最少乘车次数。

while (!que.empty()) { // 队列不为空就继续

int x = que.front(); // 取出队首的路线x

que.pop(); // 弹出队首

for (int y = 0; y < n; y++) { // 遍历所有路线y

// 条件1：路线x和y能换乘；条件2：路线y没被访问过

if (edge[x][y] && dis[y] == -1) {

dis[y] = dis[x] + 1; // 乘车次数+1

que.push(y); // 把y加入队列，继续搜索

}

}}

还是举例子：

队列里初始是路线 0，dis [0]=1；

取出路线 0，遍历所有路线 y：

y=1：edge [0][1]=true，dis [1]=-1 → dis [1] = 1+1=2，加入队列；

其他路线：edge [0][y]=false，跳过；

接下来处理队列里的路线 1，继续找能换乘的路线……

4.5 第五步：计算最终结果 —— 找到达终点的最少乘车次数

int ret = INT_MAX; // 初始设为最大整数// 遍历所有经过终点T的路线for (int bus : rec[T]) {

if (dis[bus] != -1) { // 这条路线能到达

ret = min(ret, dis[bus]); // 取最小值

}}// 没找到就返回-1，否则返回最少乘车次数return ret == INT_MAX ? -1 : ret;

比如终点 T 是 9，rec [9] = [1]，dis [1]=2 → 最少乘车次数就是 2（换乘 1 次）。

4.6 辅助函数：手动输入路线和站点

这部分代码很简单，就是让用户输入路线数量、每条路线的站点数和站点编号，最终返回一个二维数组routes，比如routes = [[1,3,5],[5,7,9]]。

4.7 主函数：整合所有步骤

主函数的逻辑就是：

调用inputRoutes()让用户输入路线；

输入起点 S 和终点 T；

调用numBusesToDestination()计算最少乘车次数；

输出结果。

五、举个完整例子：算法怎么跑？

用一个具体的例子，把整个流程走一遍，你就全懂了。

输入

路线数量：2

路线 1（索引 0）：1 3 5

路线 2（索引 1）：5 7 9

起点 S=1，终点 T=9

执行过程

特殊情况：S≠T，继续；

预处理哈希表和邻接矩阵：

rec[1] = [0]，rec[3] = [0]，rec[5] = [0,1]，rec[7] = [1]，rec[9] = [1]；

edge[0][1] = edge[1][0] = true；

初始化 BFS：

rec [S=1] = [0] → dis [0] = 1，队列加入 0；

BFS 搜索：

取出队列里的 0，遍历 y=0 到 1：

y=1：edge [0][1]=true，dis [1]=-1 → dis [1] = 2，队列加入 1；

计算结果：

rec[T=9] = [1]，dis[1]=2 → ret=2；

输出：最少需要乘坐 2 辆公交车（换乘 1 次）。

六、优化点对比：为什么这个算法更快？

和之前的全量遍历算法比，这个优化版本的核心优势在两个地方：

简单说，传统算法是 “用到了再算”，优化算法是 “提前算好，用到了直接查”，路线越多，优化效果越明显。

七、算法的优缺点和改进方向

7.1 优点

效率高：预处理后，搜索过程几乎没有重复计算，适合路线多的场景；

逻辑清晰：预处理 + 搜索的两步走，分工明确，容易理解；

实用性强：哈希表和邻接矩阵都是常用数据结构，代码容易落地。

7.2 缺点

空间开销：邻接矩阵的空间复杂度是 O (n²)，如果路线数 n 特别大（比如 1000 条），矩阵会占用较多内存；

只算次数，不返回路线：这个算法只能算出最少坐几条线，但没法返回具体的路线顺序（比如路线 0→路线 1），如果需要输出路线，还得在 BFS 里记录路径；

不考虑站点数：和之前的算法一样，只关注乘车次数，不考虑总坐多少站。

7.3 改进方向

优化空间：把邻接矩阵换成邻接表（比如vector<vector<int>> adj），只存能换乘的路线，节省内存；

记录具体路线：在 BFS 时，用一个数组prev记录每条路线的上一条路线，最后回溯出完整的路线序列；

多目标优化：加入站点数的权重，比如 “乘车次数 ×2 + 总站点数”，用加权 BFS 找综合最优解。

八、总结

这篇文章讲的算法，核心是 “提前预处理，减少重复计算”—— 用哈希表快速定位 “站点对应的路线”，用邻接矩阵快速判断 “路线能否换乘”，再结合 BFS 的逐层搜索，高效找到最少乘车次数。

相比于传统的全量遍历算法，这个优化版本在路线数量较多时优势明显，而且逻辑并不复杂，只要理解了 “哈希表存站点 - 路线”“邻接矩阵存路线 - 换乘” 这两个核心点，就能轻松上手。

五、举个完整例子：算法怎么跑？

用一个具体的例子，把整个流程走一遍，你就全懂了。

输入

路线数量：2

路线 1（索引 0）：1 3 5

路线 2（索引 1）：5 7 9

起点 S=1，终点 T=9

执行过程

特殊情况：S≠T，继续；

预处理哈希表和邻接矩阵：

rec[1] = [0]，rec[3] = [0]，rec[5] = [0,1]，rec[7] = [1]，rec[9] = [1]；

edge[0][1] = edge[1][0] = true；

初始化 BFS：

rec [S=1] = [0] → dis [0] = 1，队列加入 0；

BFS 搜索：

取出队列里的 0，遍历 y=0 到 1：

y=1：edge [0][1]=true，dis [1]=-1 → dis [1] = 2，队列加入 1；

计算结果：

rec[T=9] = [1]，dis[1]=2 → ret=2；

输出：最少需要乘坐 2 辆公交车（换乘 1 次）。

六、优化点对比：为什么这个算法更快？

和之前的全量遍历算法比，这个优化版本的核心优势在两个地方：

简单说，传统算法是 “用到了再算”，优化算法是 “提前算好，用到了直接查”，路线越多，优化效果越明显。

七、算法的优缺点和改进方向

7.1 优点

效率高：预处理后，搜索过程几乎没有重复计算，适合路线多的场景；

逻辑清晰：预处理 + 搜索的两步走，分工明确，容易理解；

实用性强：哈希表和邻接矩阵都是常用数据结构，代码容易落地。

7.2 缺点

空间开销：邻接矩阵的空间复杂度是 O (n²)，如果路线数 n 特别大（比如 1000 条），矩阵会占用较多内存；

只算次数，不返回路线：这个算法只能算出最少坐几条线，但没法返回具体的路线顺序（比如路线 0→路线 1），如果需要输出路线，还得在 BFS 里记录路径；

不考虑站点数：和之前的算法一样，只关注乘车次数，不考虑总坐多少站。

7.3 改进方向

优化空间：把邻接矩阵换成邻接表（比如vector<vector<int>> adj），只存能换乘的路线，节省内存；

记录具体路线：在 BFS 时，用一个数组prev记录每条路线的上一条路线，最后回溯出完整的路线序列；

多目标优化：加入站点数的权重，比如 “乘车次数 ×2 + 总站点数”，用加权 BFS 找综合最优解。

八、总结

这篇文章讲的算法，核心是 “提前预处理，减少重复计算”—— 用哈希表快速定位 “站点对应的路线”，用邻接矩阵快速判断 “路线能否换乘”，再结合 BFS 的逐层搜索，高效找到最少乘车次数。

相比于传统的全量遍历算法，这个优化版本在路线数量较多时优势明显，而且逻辑并不复杂，只要理解了 “哈希表存站点 - 路线”“邻接矩阵存路线 - 换乘” 这两个核心点，就能轻松上手。