公交系统这个程序设计训练题，我几乎每年带学生做课程设计时都会碰到。乍一听名字挺普通，等你真正动手去实现才发现，它把数据结构里的图论、搜索算法、工程实现全部串起来了。你在一个控制台程序里加站点、配线路、查路径，最后写出来的东西不只是一个命令行玩具，而是一个能回答“从A站到B站最短怎么走、最少换乘怎么走”的完整查询系统。这篇文章我就拿“3-15 公交系统”这个题作为案例，把从题目拆解、数据结构设计、算法选型，到完整实现和排错的全过程讲一遍。内容偏实战，适合正在做课程设计的学生，也适合想拿图论算法练手、想搞明白最短路径落地的同学。

这类题看起来不难，但有个隐藏门槛：它不像教科书上的纯最短路题目那样，给了图就能跑。公交系统里“换乘”是一个绕不开的业务约束，而把“换乘次数”和“最短时间”同时处理好，才是这道训练题真正想考你的地方。

1. 题目解读与需求拆解

1.1 这道题到底在考什么

先从题面看。公交系统通常要求你维护若干条公交线路，每条线路由一串站点组成，站点之间有行驶时间或者距离。用户输入起点和终点，系统要给出可行的乘车方案。看起来是个图论题，但它和平时的裸最短路题有几处明显不同。

第一，图不是直接给你的。你需要自己决定站点之间怎么连边，线路信息怎么存储。这一步叫做“建图”，很多人栽在这里。第二，求最短路径时，不能只考虑行驶时间，还要考虑换乘。真实场景里，换乘一次比多坐两站更让人头疼，所以算法结果要能体现“换乘少”这个偏好。第三，输出要符合人的阅读习惯，不能只输出“最短距离是42”，而要输出“先坐X路到Y站，再换乘Z路到W站”。

我后来给学生讲这个题时，习惯把它的考点归纳成三块：抽象建模能力、数据结构选型能力、算法改造能力。这三块正好对应一个程序员拿到真实需求后最核心的基本功。

1.2 把需求拆成可以写代码的清单

拿到题目别急着写代码，先做需求拆解。我通常会把“公交系统”拆成下面这些功能点：

• 线路初始化：要能录入线路编号、经过的站点顺序、相邻站点之间的行驶时间。
• 可达性判断：任意两个站点之间到底通不通。
• 最少换乘查询：在“换乘次数最少”的前提下给出方案，不关心时间长短。
• 最短时间查询：综合考虑行驶时间和换乘等待时间，算出总耗时最短的方案。
• 路径结果展示：把站点序列、乘坐线路、换乘地点都打印清楚。

这个清单看起来简单，但它直接影响后面的建模方式。如果你只做前两项，那用一个普通的站点图就够了；但要做第三项和第四项，你就必须面对“换乘”这个业务概念的建模问题。所以接下来的关键点，就是怎么把“换乘”翻译成图论语言。

2. 建模方案对比：为什么换乘是核心难点

2.1 两种常见的图建模方式

第一种方案是最直觉的：站点作为图节点，两个站点如果被某条公交线路直接连通，就在它们之间连一条边。这个思路写起来很快，但它有个致命问题——无法准确统计换乘次数。

举个例子，站点A和站点B之间有直达线路L1，B和C之间有直达线路L2，而L1和L2都经过B站。用站点图建完以后，A到C的路径是A-B-C，中间经过B。但你根本不知道B处的“经过”到底算不算换乘。如果只算图上的边数，A到C是两条边，没法表达“这已经换了1次车”这个信息。

第二种方案是引入“线路维度”。图节点不是纯粹的站点，而是“站点+线路”的组合，比如(A, L1)表示“通过L1到达站点A”。每一个状态知道乘客当前坐在哪条线上，换乘就成了从一个状态跳到另一个状态的动作：从(A, L1)到(A, L2)就表示在A站换车。这就是分层图思想，也是解决这类题最可靠的方案。

这两种方案我实际都用过。站点图写起来快，但一旦需求里要求“最少换乘”，就得各种补丁；而分层图虽然初期多写一点代码，后面的扩展空间却大得多。做课程设计时我建议直接用分层图思路，后面做动态规划、做实时调度都能复用。

2.2 边权怎么设计才合理

图建好了，还要给边赋权。这里有个容易被忽略的点：换乘是有代价的。真实世界里，换乘需要等车，还有步行到站台的额外时间，所以不能把换乘当成零成本操作。

比较常见的做法是给换乘设置一个等待时间常数，比如5分钟。这样“最短时间查询”就变成：在所有可行方案中，最小化“行驶时间总和 + 换乘次数 × 5分钟”。这个参数设计得非常巧妙，它让算法在“快”和“少换乘”之间自动做了折中。如果等待时间设为0，算法会倾向于频繁换乘，因为换乘可能让你搭上更快的线路；如果等待时间设得很大，算法又几乎退化成“最少换乘优先”。

当然，如果题目只要求最少换乘次数，那就把每条线路内部的边权设为0，换乘边设为1，再跑最短路或BFS。要是题目要求最少票价，就把边权换成票价规则，比如“上车2元，换乘不再收费”，那换乘边权就设为0，同线路内部边权也设为0，但“上车”动作设为2元，这又变成另一种建图方式。建图方案完全跟着业务约束走，这也是为什么我说业务需求拆解比写代码更重要。

2.3 数据结构的选型与实现

结构上，我习惯把公交系统拆成两个核心表：线路表和邻接表。

线路表存的是每条线路的基础信息：

邻接表这里稍微特殊一点。对于站点图，邻接表是“站点 -> 相邻站点列表”；对于分层图，我更推荐直接用两个邻接关系：

• 线路内邻接：对于每条线路，站点i到站点i+1有一条权值为行驶时间的边。
• 换乘邻接：在同一个站点，从线路L1可以跳到线路L2，权值为换乘等待时间。

这样做的好处是编码逻辑和现实场景一一对应。你不用去维护一个巨大的二维状态矩阵，只需要在线路数据里做遍历。实现上，我会用vector存线路，用map或unordered_map建立“站点 -> 经过该站点的线路列表”的索引，查询时先用索引找到相关线路，再在算法内部做状态扩展。

3. 核心算法：BFS少换乘与Dijkstra短时间

3.1 最少换乘的BFS解法

如果只求最少换乘次数，有一个非常优雅的解法，连Dijkstra都不用。因为“换乘次数”这个指标天然是等权的：换乘一次就是一个单位，所以BFS从起点扩散到终点的层数就是最少换乘次数。

具体做法是：把每条线路看作一个节点，线路之间有共同站点就认为可以换乘。于是先建立“线路图”，从包含起点的所有线路出发做BFS，扩展到包含终点的线路，层数减一就是换乘次数。如果起点和终点在同一条线路上，换乘次数就是0。

举个例子。线路L1经过A、B、C，线路L2经过C、D、E，线路L3经过E、F。查A到F：先从L1出发，L1和L2在C站相交，所以从L1可以换到L2；L2和L3在E站相交，再从L2换到L3。BFS从L1走到L3需要两层，换乘次数就是1次。这个思路非常直观，代码也短。

不过要注意一个细节：BFS的访问标记要标记线路，不是标记站点。因为同一个站点可能被多条线路经过，A从L1来和从L2来，后续能换乘的线路集合完全不同，只标记站点会漏掉方案。这个坑我见过不少同学踩过。

3.2 最短时间的Dijkstra状态扩展

最短时间查询比最少换乘复杂，因为行驶时间不相等，而且还要把换乘等待时间混进去。这时要用Dijkstra，但状态不能只是“站点”，必须带上“当前线路”。

我的实现里，每个状态用三元组表示：(当前站点, 当前所在线路, 累计时间)。优先队列按累计时间从小到大弹出，每次扩展时做两件事。

第一件事，沿着当前线路继续往前开。假设当前状态是(A, L1, 10)，L1的下一站是B，行驶时间是5分钟，那么可以得到新状态(B, L1, 15)。这个操作对应“不换车，继续坐”。

第二件事，在当前站点换乘到其他线路。假设A站除了L1还有L2经过，换乘等待时间是4分钟，那么从(A, L1, 10)可以推出新状态(A, L2, 14)。这个操作对应“在A站下车，等4分钟，换乘L2”。

反复执行这两种扩展，直到所有站点都收敛，终点的最小时间就是答案。为了不让算法退化，我通常用优先队列优化，复杂度是O(E log V)，E是状态转移边的数量，V是“站点×线路”组合数。对课程设计的小数据量来说，性能完全够用。

这里有个很关键的处理：dist数组要开成二维的，dist[站点][线路]表示“乘某条线路到达该站点的最少时间”。如果只开一维dist[站点]，你会丢失线路信息，导致换乘判断出错。想象一下，你先坐L1到A站花了10分钟，之后从A站换乘L2；另一个方案是坐L2直达A站花了12分钟。单看A站，最优是10分钟，但10分钟这条状态来自L1，它在A站换乘L2要额外付等待时间；而12分钟的L2状态可以直接在A站继续坐L2。如果只保留最小时间，信息不够完整，结果就偏了。

3.3 路径输出：从状态回溯到乘车方案

算法跑完，还得解决“怎么给人看”的问题。Dijkstra跑完后的结果通常是一堆距离数值，但要输出乘车方案，就必须记录每个状态是从哪个状态转移来的。

我在代码里会用pre数组记录前驱。pre[(B, L1)] = (A, L1)表示“从A站乘L1到了B站”；pre[(A, L2)] = (A, L1)表示“在A站从L1换乘到了L2”。最后从终点状态一路回溯到起点，会得到一个状态序列。

拿到状态序列以后，要做一步后处理：把连续相同线路的站点合并成一段，遇到线路变化的节点就标记成“换乘站”。最后输出格式大概是：

从A站乘坐L1路 乘坐3站到达C站 在C站换乘L2路 乘坐2站到达F站

这一步看起来不起眼，但它是整个系统体验的关键。算法再漂亮，如果输出是一堆数字和括号，用户根本没法用。我经常跟学生说，写算法题可以只输出数值，但写系统必须把结果翻译成人话。

4. 完整实操：从零手写一个公交查询系统

4.1 模块划分与类设计

为了方便扩展，我会把系统拆成几个独立模块，而不是把所有逻辑都塞进main函数里。推荐下面的模块划分：

• 数据模型层：定义站点、线路、状态节点的数据结构。
• 图构建层：读取线路数据，建立线路索引和状态转移关系。
• 查询算法层：实现最少换乘BFS和最短时间Dijkstra。
• 结果输出层：把算法结果格式化为乘车方案。

对应到C++代码，我会设计三个核心类。

BusSystem类是总控，负责初始化和对外提供查询接口。BusLine类封装一条线路的站点顺序和区间时间。QueryResult类用来承载查询结果，包括是否可达、总时间、换乘次数、具体的乘车步骤。

这样设计的好处是，main函数里只需要几行代码就能完成整个流程：读数据、建系统、查路线、打印结果。后面加功能也不会把某个文件改得乱七八糟。

4.2 核心代码逐段讲解

下面我给出一段精简但可运行的核心代码框架，用C++实现，重点展示Dijkstra方法。

#include <bits/stdc++.h> using namespace std; struct Edge { int to; int lineId; int cost; }; class BusSystem { private: // lineId -> 线路经过的站点和区间时间 vector<vector<int>> lineStops; vector<vector<int>> lineTimes; // station -> 经过该站点的所有线路 unordered_map<int, vector<int>> stationToLines; int waitTime = 5; public: void addLine(const vector<int>& stops, const vector<int>& times) { int lineId = lineStops.size(); lineStops.push_back(stops); lineTimes.push_back(times); for (int s : stops) { stationToLines[s].push_back(lineId); } } int shortestTime(int start, int target) { // 状态：站点 * 线路 // dist[station][line] = 最小时间 unordered_map<int, unordered_map<int, int>> dist; // 优先级队列：时间，站点，线路 priority_queue<tuple<int,int,int>, vector<tuple<int,int,int>>, greater<>> pq; // 起点初始化：从起点可乘坐的所有线路出发，上车不算换乘 for (int lineId : stationToLines[start]) { dist[start][lineId] = 0; pq.push({0, start, lineId}); } while (!pq.empty()) { auto [time, station, lineId] = pq.top(); pq.pop(); if (time > dist[station][lineId]) continue; // 到达终点，可以直接返回（Dijkstra首次弹出必然最优） if (station == target) return time; // 1. 沿当前线路继续向前 auto& stops = lineStops[lineId]; auto& times = lineTimes[lineId]; for (int i = 0; i + 1 < stops.size(); ++i) { if (stops[i] == station) { int nxt = stops[i + 1]; int cost = times[i]; if (!dist[nxt].count(lineId) || time + cost < dist[nxt][lineId]) { dist[nxt][lineId] = time + cost; pq.push({time + cost, nxt, lineId}); } } } // 2. 在当前站点换乘到其他线路 for (int nxtLine : stationToLines[station]) { if (nxtLine == lineId) continue; int newTime = time + waitTime; if (!dist[station].count(nxtLine) || newTime < dist[station][nxtLine]) { dist[station][nxtLine] = newTime; pq.push({newTime, station, nxtLine}); } } } return -1; } };

需要注意几个细节。第一，起点可能有多个线路经过，我全部初始化成0，表示乘客在起点随便上一辆车，不产生换乘时间。第二，Dijkstra弹出目标站点时可以直接返回，因为优先队列保证了当前弹出的就是最小时间，后面不可能再出现更优解。第三，换乘时我跳过了同线路，因为同一线路不需要换乘，继续坐就行。

上面这份代码只返回了最短时间。实际做课程设计时，还要补pre数组来记录路径，这个逻辑和dist的更新是同步的，代码量不大，但能让你的输出从“一个数字”变成“一份攻略”。

4.3 测试数据构造与结果验证

算法写完不能直接交，一定要自己构造测试数据验证。我常用的测试网络很简单，但覆盖的Case很全。

假设有4个站点：1、2、3、4。线路L1为1-2-3，区间时间分别是5和6；线路L2为3-4，区间时间为7；线路L3为1-4，区间时间为15。也就是说，既有“直达线路”又有“需要换乘的线路”。

查1到4的最短时间：直接坐L3，15分钟到。坐L1到3再换L2，时间是5+6+5+7=23分钟。所以程序应该输出15。这个用例可以验证Dijkstra不会因为换乘次数少而选出一条绕远路线。

换一个用例，查1到3：坐L1直达，时间为5+6=11；如果坐L3到4再换L2到3，时间是15+5+7=27，虽然换乘次数看起来更少，实际更慢。程序应该选L1直达。

再构造一个不连通场景：站点5和6之间只有一条线路L4，查询1到5应该返回-1。这一步能验证程序对不可达情况的处理，很多同学的代码在不可达时会死循环，多半是优先级队列比较器或者访问标记写错了。

我实测下来，一个包含10个站点、4条线路的测试网络，跑几百次随机查询，单次查询都在毫秒级。课程设计的规模完全不用考虑性能优化，把逻辑写对就行。

5. 常见问题排查与扩展思路

5.1 调试中踩过的经典坑

这部分是我最想分享的，因为很多坑不是题目有多难，而是细节太容易出错。我列一个速查表，都是我实际调试中遇到过的：

还有一个很容易被忽略的点：公交线路通常是双向运营的，也就是1-2-3这条线，实际既能从1坐到3，也能从3坐到1。建图时要考虑双向，否则查询结果会漏掉一半方案。如果题目里明确线路单向，那就在addLine的时候做区分。

5.2 这个系统还能怎么升级

做完基础版以后，我建议大家不要急着交差，试着加一些扩展功能。这些扩展能让你在答辩或者课程报告里多出很多可讲的内容。

第一个扩展是票价计算。把换乘边权和线路内部边权改成票价规则，比如“上车2元，同线路内不再收费，换乘再付2元”。这个模型只需要改几个边权定义，算法本身不用动，但能让系统更贴近真实需求。

第二个扩展是查询结果排序。很多场景下用户不只需要一条最优路径，而是想要“最少时间”“最少换乘”“最少步行”等几种方案。你可以把Dijkstra改成K短路，或者用多目标优化，先算出候选集再按不同偏好排序。

第三个扩展是从控制台搬到Web或者图形界面。把算法层做成独立模块后，外面套一层HTTP接口或者Qt界面，就变成了一个可以给别人演示的完整应用。我以前有个学生用Qt做了个公交线路地图，站点画在地图上，查询路径后高亮显示，效果比控制台好了不止一个档次。

第四个方向是实时动态数据。真实公交系统里，路况变化、车辆晚点都会影响路径选择。你可以用定时器模拟实时数据，每过一段时间更新某条线路的行驶时间，再用动态最短路算法重算最优路线。这个方向适合想往算法或者后端方向发展的同学，扩展性很强。

我个人在实际操作中的体会是，公交系统这个题最难的不是那些算法，而是把“换乘”这个现实中很自然的概念，抽象成程序里能被计算的东西。一旦你理解了分层图或者状态扩展的思路，再去写最少换乘BFS、最短时间Dijkstra，都是水到渠成的事。这个思维过程，远比最后交上去的代码更值钱。