公交系统这个程序设计训练题我几乎每年带学生做课程设计时都会碰到。乍一听名字挺普通等你真正动手去实现才发现它把数据结构里的图论、搜索算法、工程实现全部串起来了。你在一个控制台程序里加站点、配线路、查路径最后写出来的东西不只是一个命令行玩具而是一个能回答“从A站到B站最短怎么走、最少换乘怎么走”的完整查询系统。这篇文章我就拿“3-15 公交系统”这个题作为案例把从题目拆解、数据结构设计、算法选型到完整实现和排错的全过程讲一遍。内容偏实战适合正在做课程设计的学生也适合想拿图论算法练手、想搞明白最短路径落地的同学。这类题看起来不难但有个隐藏门槛它不像教科书上的纯最短路题目那样给了图就能跑。公交系统里“换乘”是一个绕不开的业务约束而把“换乘次数”和“最短时间”同时处理好才是这道训练题真正想考你的地方。1. 题目解读与需求拆解1.1 这道题到底在考什么先从题面看。公交系统通常要求你维护若干条公交线路每条线路由一串站点组成站点之间有行驶时间或者距离。用户输入起点和终点系统要给出可行的乘车方案。看起来是个图论题但它和平时的裸最短路题有几处明显不同。第一图不是直接给你的。你需要自己决定站点之间怎么连边线路信息怎么存储。这一步叫做“建图”很多人栽在这里。第二求最短路径时不能只考虑行驶时间还要考虑换乘。真实场景里换乘一次比多坐两站更让人头疼所以算法结果要能体现“换乘少”这个偏好。第三输出要符合人的阅读习惯不能只输出“最短距离是42”而要输出“先坐X路到Y站再换乘Z路到W站”。我后来给学生讲这个题时习惯把它的考点归纳成三块抽象建模能力、数据结构选型能力、算法改造能力。这三块正好对应一个程序员拿到真实需求后最核心的基本功。1.2 把需求拆成可以写代码的清单拿到题目别急着写代码先做需求拆解。我通常会把“公交系统”拆成下面这些功能点线路初始化要能录入线路编号、经过的站点顺序、相邻站点之间的行驶时间。可达性判断任意两个站点之间到底通不通。最少换乘查询在“换乘次数最少”的前提下给出方案不关心时间长短。最短时间查询综合考虑行驶时间和换乘等待时间算出总耗时最短的方案。路径结果展示把站点序列、乘坐线路、换乘地点都打印清楚。这个清单看起来简单但它直接影响后面的建模方式。如果你只做前两项那用一个普通的站点图就够了但要做第三项和第四项你就必须面对“换乘”这个业务概念的建模问题。所以接下来的关键点就是怎么把“换乘”翻译成图论语言。2. 建模方案对比为什么换乘是核心难点2.1 两种常见的图建模方式第一种方案是最直觉的站点作为图节点两个站点如果被某条公交线路直接连通就在它们之间连一条边。这个思路写起来很快但它有个致命问题——无法准确统计换乘次数。举个例子站点A和站点B之间有直达线路L1B和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 数据结构的选型与实现结构上我习惯把公交系统拆成两个核心表线路表和邻接表。线路表存的是每条线路的基础信息字段含义lineId线路编号stops按顺序经过的站点列表travelTime相邻站点间的行驶时间数组邻接表这里稍微特殊一点。对于站点图邻接表是“站点 - 相邻站点列表”对于分层图我更推荐直接用两个邻接关系线路内邻接对于每条线路站点i到站点i1有一条权值为行驶时间的边。换乘邻接在同一个站点从线路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可以换到L2L2和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 - 线路经过的站点和区间时间 vectorvectorint lineStops; vectorvectorint lineTimes; // station - 经过该站点的所有线路 unordered_mapint, vectorint stationToLines; int waitTime 5; public: void addLine(const vectorint stops, const vectorint 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_mapint, unordered_mapint, int dist; // 优先级队列时间站点线路 priority_queuetupleint,int,int, vectortupleint,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的最短时间直接坐L315分钟到。坐L1到3再换L2时间是565723分钟。所以程序应该输出15。这个用例可以验证Dijkstra不会因为换乘次数少而选出一条绕远路线。换一个用例查1到3坐L1直达时间为5611如果坐L3到4再换L2到3时间是155727虽然换乘次数看起来更少实际更慢。程序应该选L1直达。再构造一个不连通场景站点5和6之间只有一条线路L4查询1到5应该返回-1。这一步能验证程序对不可达情况的处理很多同学的代码在不可达时会死循环多半是优先级队列比较器或者访问标记写错了。我实测下来一个包含10个站点、4条线路的测试网络跑几百次随机查询单次查询都在毫秒级。课程设计的规模完全不用考虑性能优化把逻辑写对就行。5. 常见问题排查与扩展思路5.1 调试中踩过的经典坑这部分是我最想分享的因为很多坑不是题目有多难而是细节太容易出错。我列一个速查表都是我实际调试中遇到过的问题现象可能原因解决办法查询结果始终偏大换乘等待时间被重复计算检查换乘边是否只在“线路变化”时触发同线路不需要等待输出路径包含同一站点两次线路中存在环路或者重复经过加访问标记扩展时过滤已访问站点不可达时程序卡死优先队列比较器写反或dist数组未初始化比较器用greaterdist用极大值初始化最少换乘结果错误BFS标记了站点而不是线路改成标记线路或状态设为“站点线路”组合起点和终点同站但输出可达终点判断写在整个扩展之前先判断starttarget再初始化避免误判换乘次数正确但总时间不对换乘等待时间设置或边权单位不一致确认时间单位统一等待时间和行驶时间用同一单位还有一个很容易被忽略的点公交线路通常是双向运营的也就是1-2-3这条线实际既能从1坐到3也能从3坐到1。建图时要考虑双向否则查询结果会漏掉一半方案。如果题目里明确线路单向那就在addLine的时候做区分。5.2 这个系统还能怎么升级做完基础版以后我建议大家不要急着交差试着加一些扩展功能。这些扩展能让你在答辩或者课程报告里多出很多可讲的内容。第一个扩展是票价计算。把换乘边权和线路内部边权改成票价规则比如“上车2元同线路内不再收费换乘再付2元”。这个模型只需要改几个边权定义算法本身不用动但能让系统更贴近真实需求。第二个扩展是查询结果排序。很多场景下用户不只需要一条最优路径而是想要“最少时间”“最少换乘”“最少步行”等几种方案。你可以把Dijkstra改成K短路或者用多目标优化先算出候选集再按不同偏好排序。第三个扩展是从控制台搬到Web或者图形界面。把算法层做成独立模块后外面套一层HTTP接口或者Qt界面就变成了一个可以给别人演示的完整应用。我以前有个学生用Qt做了个公交线路地图站点画在地图上查询路径后高亮显示效果比控制台好了不止一个档次。第四个方向是实时动态数据。真实公交系统里路况变化、车辆晚点都会影响路径选择。你可以用定时器模拟实时数据每过一段时间更新某条线路的行驶时间再用动态最短路算法重算最优路线。这个方向适合想往算法或者后端方向发展的同学扩展性很强。我个人在实际操作中的体会是公交系统这个题最难的不是那些算法而是把“换乘”这个现实中很自然的概念抽象成程序里能被计算的东西。一旦你理解了分层图或者状态扩展的思路再去写最少换乘BFS、最短时间Dijkstra都是水到渠成的事。这个思维过程远比最后交上去的代码更值钱。
