这段时间常在训练题里看到“公交系统”这类名字第一眼觉得不就是个图论最短路真要动手才发现难点根本不在算法本身而在怎么把一个现实中很自然的换乘问题翻译成计算机能算的东西。我当初在这道题上卡了整整一个晚上反复调整建图方式才跑通。这篇文章就把我对这类题目的完整思考和踩坑过程整理出来从题面拆解、数据结构选型到两套不同目标的算法实现和边界测试一次性讲透。1. 题面拆解公交系统到底在考什么1.1 看似是图论其实考的是建图方式先还原一下这道题常见的题面。给定若干条公交线路每条线路按顺序经过一系列站点编号再给若干个查询每个查询给起点站和终点站要求输出从起点到终点需要的最少换乘次数或者最少经过的站点数有的版本两个都问。很多人的第一反应是站点就是图的节点线路就是边然后跑最短路。这个方向没错但问题出在建图的粒度上。如果一条线路有十几个站你直接把这条线路当成一条从首站到尾站的边那就大错特错了——公交车只能沿着线路逐站走不能跳站。你从第1站上车不可能直接坐到第10站而不经过中间那些站点。所以建图时必须按照线路的相邻关系来连边即第i站连第i1站而不是首尾相连。这道题真正想考察的第一个能力就是把文字描述转化成图模型。同一条线路上的相邻站点之间有了一条边意味着你可以坐着这条线从一站挪到相邻站换乘则发生在两条线路共同经过的某个站点。把这些关系梳理清楚后面的所有算法才有意义。1.2 换乘次数和站点数两种目标的本质差异这道题最大的陷阱在于同样一张公交网络问最少换乘次数和最少经过站点数是两种完全不同的优化目标建模方式截然不同。最少换乘次数你关心的是我坐了几段不同的线路至于每段线路上坐了几站根本无所谓。所以状态应该跟线路绑定而不是跟站点绑定。最少经过站点数你关心的是总共经过多少个站同一线路连续移动会产生累加的代价所以每移动一站算一个代价这天然对应加权图最短路。我见过不少同学用一套代码去处理两个问题结果换乘最少的时候绕了远路或者站数最少但换乘了七八次。说到底是因为没有意识到这两种目标背后的状态空间不一样。下面两节分别给出两种建模方案和完整实现先说最少换乘再说最少站数。实际训练时建议两个版本分开写逻辑更清晰也利于调试。2. 建图阶段车站与线路的数据结构选型2.1 邻接表还是邻接矩阵关键看数据规模程序训练题一般会限定数据范围比如站点数不超过500线路数不超过100每条线路站点数不超过50。这个规模下邻接矩阵和邻接表都能跑但选择哪一个是会影响解题思路的。如果只求最少换乘次数一个非常经典的做法是在线路编号之间建图而不是在站点编号之间建图。因为换乘的本质是从一条线路换到另一条线路两条线路只要有共同站点就能换乘换乘代价记为1或0看具体定义。这样一来图的节点是线路若线路A和线路B有公共站点则A与B之间有一条边权重为1表示换乘一次。起点站和终点站的处理方式是找出起点站属于哪些线路集合S终点站属于哪些线路集合T然后跑一个从任一起始线路到任一目标线路的最短路最短路长度就是最少换乘次数。注意如果起点站和终点站在同一条线路上那答案直接是0次换乘这是很多测试用例卡人的地方。当使用线路图时图的节点数是线路数通常比站点数少一个数量级用邻接矩阵存起来非常舒服。我习惯开一个vector数组记录每条线路经过的站点同时开一个mapint, vectorint stationToLines记录每个站点被哪些线路经过这样在建图时只需要遍历每对线路是否有共同站点就行。2.2 把线路站序变成可检索的索引——线路到车站、车站到线路具体来说我会维护两份数据const int MAX_LINE 105; const int MAX_STATION 505; vectorint lines[MAX_LINE]; // 每条线路依次经过的站点 vectorint stationToLines[MAX_STATION]; // 每个站点属于哪些线路读取输入时对每条线路先把站点序列完整读入lines[i]然后对每个站点station往stationToLines[station]里加入线路编号i。要特别注意去重因为同一条线路中站点不重复题面一般保证但多条线路可能共享站点这在后面处理换乘时才是有效的换乘点。有了这两份索引判断两条线路能否换乘只需要看它们是否有公共站点即可。最朴素的做法是直接二重循环对比但更稳妥的方式是对每条线路的站点集合求交集。考虑到数据范围不大我通常直接用一个布尔数组标记线路i上的所有站点再遍历线路j的站点只要有命中就说明两条线路连通。vectorvectorint lineGraph(MAX_LINE, vectorint(MAX_LINE, INF)); // 对每条线路 for (int i 0; i n; i) { bool visited[MAX_STATION] {false}; for (int s : lines[i]) visited[s] true; for (int j i 1; j n; j) { for (int s : lines[j]) { if (visited[s]) { lineGraph[i][j] lineGraph[j][i] 1; break; } } } }这里距离权重设为1含义是换乘一次。同一条线路内部的相邻站点之间的权重不是我们在这里考虑的问题因为换乘次数根本不关心路程长短。3. 算法方案一最少换乘的 BFS 解法3.1 状态设计把上了哪条线路放进状态最少换乘问题的经典解法是在线路图上做BFS。为什么用BFS而不是Dijkstra因为线路图中每条边的权重都是1BFS天然就能求出无权图的最短路时间复杂度O(VE)比Dijkstra更省编码也更简单。状态设计上我让dist[i]表示从起始线路集合到线路i的最少换乘次数初始状态把所有包含起点站的线路距离设为0。然后用队列做广度优先扩散int bfs(vectorvectorint graph, int start, int target, vectorint startLines, vectorint targetLines) { queueint q; vectorint dist(MAX_LINE, INF); for (int line : startLines) { dist[line] 0; q.push(line); } while (!q.empty()) { int cur q.front(); q.pop(); for (int nxt 0; nxt graph.size(); nxt) { if (graph[cur][nxt] ! INF dist[nxt] INF) { dist[nxt] dist[cur] 1; q.push(nxt); } } } int ans INF; for (int line : targetLines) { ans min(ans, dist[line]); } return ans; }这里有一个关键细节初始状态是所有包含起点站的线路而不是某个具体站点。因为没有必要纠结具体在哪一站上游览——你的起点是一个站能上车的线路有好几条BFS的起点天然就是这些线路构成的集合。同理终点也是用targetLines集合来校验最后取这些线路中距离最小的值。这恰好反映了换乘次数这种目标的正确建模思路。3.2 边界处理与换乘定义在不少题目中换乘次数指的是从一条线路换到另一条线路的次数因此起点站上车不算一次换乘最后一次下车也不算一次换乘。我们的建图方式天然满足这个定义起点站所在的线路dist为0之后每换乘一次dist加1。终点站所在的线路只要有距离值就说明可以通过这么多次换乘到达。但有一种情况需要额外注意如果起点站和终点站之间根本不存在可达路径那么BFS结束后所有targetLines的dist仍然为INF此时需要输出-1或无解。测试用例里基本必有一个这种情形绝对不能漏。还有一种需要注意的情况是环线。有些公交线路可能是环形的比如1-2-3-1这样在读取线路站点时最后一个站可能是起点站的重复。我的建议是读入时不做特殊处理建图时重复站点不会影响换乘判断因为站点集合没有变化但在用线路站点序列计算最少经过站点数时环线会导致重复经过某个站点这时需要额外谨慎。不过最少换乘场景下环线不会产生额外影响因为换乘只看集合。3.3 日常踩坑忘了处理同线路直达这是这道题出错频率最高的一个点。假设起点站和终点站都在3路线上那么答案应该是0因为根本不需要换乘。但如果你的初始入队逻辑只处理了startLines而忘了特判BFS结果很可能算出一个比0大的数或者在目标线路集合中根本找不到距离为0的线路因为目标线路就在起始线路集合中dist应该是0但如果初始化逻辑写错了就完蛋。我在实现时会单独加一个判断bool sameLine false; for (int line : startLines) { if (find(targetLines.begin(), targetLines.end(), line) ! targetLines.end()) { sameLine true; break; } } if (sameLine) return 0;注意find的时间复杂度不高因为线路数量很少。不过更优雅的做法是把startLines加入队列时同时让targetLines集合中的线路距离也是0这样BFS后取最小值自然得到0。但为了防止逻辑混乱我建议显式判断一次简单粗暴且不容易出错。另一个坑是站点编号可能不连续。题面可能说站点编号从1到N但有时会给你很大的编号比如几千甚至几万而实际参与运算的站点不到几百个。这时如果直接开vector[MAX_STATION]MAX_STATION要取到最大编号5否则越界。如果最大编号不确定就用unordered_mapint, vectorint来存站到线路的映射避免浪费内存和越界风险。4. 算法方案二最少站数的 Dijkstra 解法4.1 加权图建模同线相邻站权重为1如果要算最少经过站点数换乘次数就不够用了得换一种建模方式。这种情况下我直接在站点之间建图。两个站点如果没有在任意一条线路上相邻则没有边如果相邻则有一条权重为1的无向边或者有向边取决于题目是否允许双向坐车绝大多数公交题默认双向可达但个别题会声明单向要仔细看题。为什么权重是1而不是站数因为从站点A到相邻站点B公交车只经过一站所以把相邻站点间边的权重设为1。然后跑一次从起点站到终点站的单源最短路得到的最短距离就是最少经过的站点数严格来说这里算的是经过的边数也就是坐了几站具体题目要求经过的站点数还是经过的边数要注意区分通常边数加一才是站点数但很多题把站数定义为坐过的站数即边数需要按题面来处理。注意从这里就能看出和换乘问题的本质区别这里你在同一条线路上连续移动每次移动都会产生代价所以不能只用线路作为节点。必须把站点作为节点把同一线路相邻站点作为边。4.2 用邻接表实现 Dijkstra站点数如果不超过500用邻接矩阵或者邻接表都行但我推荐邻接表因为实际代码里你还要根据线路动态建边邻接表更方便。const int INF 0x3f3f3f3f; vectorpairint, int adj[MAX_STATION]; void buildGraph(vectorint lines[], int lineCount) { for (int i 0; i lineCount; i) { for (int j 0; j (int)lines[i].size() - 1; j) { int u lines[i][j]; int v lines[i][j 1]; adj[u].push_back({v, 1}); adj[v].push_back({u, 1}); // 根据题意决定是否双向 } } }建好图后跑标准Dijkstraint dijkstra(int start, int target) { vectorint dist(MAX_STATION, INF); priority_queuepairint, int, vectorpairint, int, greaterpairint, int pq; dist[start] 0; pq.push({0, start}); while (!pq.empty()) { auto [d, u] pq.top(); pq.pop(); if (d ! dist[u]) continue; for (auto [v, w] : adj[u]) { if (dist[v] d w) { dist[v] d w; pq.push({dist[v], v}); } } } return dist[target] INF ? -1 : dist[target]; }这里用priority_queue实现了优先队列优化。注意在松弛时一定要判断d ! dist[u]否则会重复处理旧的状态导致时间复杂度退化。这个细节在数据规模小的时候不影响但线路和站点一多性能差异立刻体现。4.3 两种方案的选择依据什么时候用BFS什么时候用Dijkstra很多人会混淆。我给出一个非常简单的判断标准如果题目问的是最少换乘次数边权必然是单位权重换乘一次等于1且状态要抽象到线路层面用BFS在线路图上做如果题目问的是最少经过站点数或最短乘车距离边权是相邻站点之间累积的单位权重必须用Dijkstra或者SPFA但非必要不推荐在站点图上做如果题目两个都问就分别建图、分别跑不要试图用一个图同时搞定。严格来说站点图上所有边权都为1的Dijkstra也可以退化成BFS但那样你需要在建图时把所有相邻站点关系展开本质上和直接用BFS差不多。不过从代码实现角度Dijkstra的模板更通用后面遇到带权图时也能直接复用所以我都建议至少掌握Dijkstra的写法。还有一种情况是题目要求最少换乘次数且每条线路可以坐很多站这时候也可以把相邻站点之间的边权设为0同线路内移动不增加换乘次数然后在站点图上求0-1 BFS。这种方法本质上是把换乘建模成从线路A的某一站下车走到同一站的线路B上车时代价加1。这个做法更贴近现实但实现起来要小心处理下车和上车的节点拆分。我在训练时优先用线路图BFS因为简单清晰不容易出错。5. 实测验证与边界情况5.1 用几组典型用例卡住常见错误实现写完代码后一定要自己构造测试用例验证。我常用的几组用例直接贴在下面每一组都对应一个典型的坑。第一组同线路直达。输入 1 2 3 1 2 3 1 3 线路13个站1-2-3 查询从1到3 期望输出 0最少换乘次数2最少经过边数这一组如果输出换乘次数为1说明你的初始入队逻辑有问题。第二组需要换乘一次。输入 2 3 1 2 3 4 5 6 1 4 查询从1到4 线路11-2-3线路24-5-6无交点 期望输出 -1无解如果这组输出一个数字而不是-1说明你没判断无解。第三组两条线路在站点2交汇。输入 2 3 1 2 3 4 2 5 1 5 查询从1到5 线路11-2-3线路24-2-5 期望输出 1换乘1次3经过边数1-2是12-4是24-5是3这组特别容易把最少站数算错因为从1出发到5可能你DFS时会找到一条经过2再回到3再换乘的绕路路径导致算出的站数很大但实际上走1-2-4-5就是最短路。第四组环线。输入 1 3 1 2 3 1 1 3 线路11-2-3-1 期望输出 0次换乘2条边1到2再到3环线会让部分人在读入时没意识到最后一个1是重复站点导致建边时出现1号站到1号站的自环影响最短路计算。解决方法是读入时去除重复首尾或者在建边时跳过u v的边。if (u ! v) { adj[u].push_back({v, 1}); adj[v].push_back({u, 1}); }5.2 数据规模与超时排查思路如果数据规模变大比如线路数到500站点到10000那么上面用邻接矩阵存线路图的方式就不行了空间会爆。此时换用unordered_set存每条线路的站点集合判断两条线路是否有公共站点遍历时用iterator扫描时间复杂度也能接受。不过对于程序设计训练这个级别邻接矩阵已经足够。超时最常见的两个原因一个是Dijkstra里没有用visited或者d ! dist[u]剪枝导致一个节点反复入队另一个是BFS里没有标记已访问线路导致线路图上的节点重复扩展。前者会导致复杂度指数级上升后者在存在大量环时会特别明显。我在实测中遇到过我把dist数组初始化为-1并且用dist[nxt] -1作为未访问的判断条件这其实是最简单也最不容易写错的方式vectorint dist(MAX_LINE, -1); dist[line] 0; // 判断条件 if (dist[nxt] -1) { dist[nxt] dist[cur] 1; q.push(nxt); }5.3 一个值得反复测试的隐藏场景起点等于终点起点等于终点时最少换乘次数为0最少经过边数也为0。这个情况极端简单但容易被人忽略因为你可能进入了从起点站上车是哪条线路的逻辑导致dist初始化为0之后又在目标线路集合中找不到匹配。所以我在代码开头统一加一个特判if (start target) { printf(0\n); continue; }别嫌多余这种特判在考试时能救你一命。6. 这类题目背后的通用套路与延伸6.1 状态图思维把原问题转化为另一个图上的最短路做完公交系统这道题你会发现它其实代表了图论算法中一类极其重要的思维模式——状态图转化。也就是说有些问题表面上不是图论题但只要把状态定义好把状态之间的转移关系定义成边把转移代价定义成边权问题就变成一个标准的最短路问题。公交系统的状态可以是当前在第几条线路上也可以是当前在哪个站点。同样是这个题目你用不同的状态定义就能得到不同的图和不同的算法。这也是为什么同一个题有BFS和Dijkstra两种解法。这种思维在后续很多题目里都会用到比如迷宫问题中状态是当前坐标已获得的钥匙集合本质上是把钥匙集合压缩成一个bitmask然后在新图上做BFS再比如八数码问题状态是棋盘排列转移是空格移动用的也是BFS哈希判重。所以公交系统只是一扇门推开它能帮你建立状态图这个底层思维后面遇到各种奇怪的搜索题和动态规划题时你都会不自觉地用它来分析。6.2 延伸从公交系统到换乘推荐、导航系统的设计再往大了说公交系统建模的技术在真实世界的导航应用里非常常见。高德地图、百度地图规划公交路线时底层逻辑就包括地铁换乘次数最少与总耗时最短的多目标优化。真实场景中更复杂的是每条线路有发车间隔、首末班时间等待时间也要计入权重不同的线路票价不同可能需要算总花费最少步行换乘距离不一样换乘代价不是固定值实时路况会导致同一条线路在不同时间权重不同。这些其实都是在基础图模型上加不同的权重函数和约束条件。你把训练题中的公交系统想明白了建图的思想、状态设计的思路、最短路算法的选型这些都是通用的将来切换到一个真实导航项目时你只需要把权重函数换成实际数据本质上并没有跳出这个框架。7. 一些实操心得和调试经验最后聊几个我在实际做题和帮同学调试时积累的小经验比较零碎但每一条都来自真实踩坑。第一读题时先看清线路是单向还是双向。很多题目默认公交可以双向乘坐但也有的题目特意加上单向行驶这时候建边时就不能对称加边。我一开始没注意结果一组测试用例始终过不了最后发现是双向边的问题。第二如果题目给的站点编号是断开的比如只有1号、5号、100号站那么用数组MAX_STATION时要开到最大编号之上否则越界。如果不确定最大值就用unordered_mapint, vectorpairint,int做邻接表。第三优先队列的比较大小时pairint,int默认先比较first再比较second所以把距离放第一位、站点编号放第二位配合greater就能得到小顶堆不需要自定义比较函数。这个写法简洁且不容易错。第四如果有多组查询尽量把图只建一次然后每个查询单独跑最短路。不要在查询里重复建图否则大数据的查询一多时间就炸了。第五代码里宁可多开数组不要用小数组。站点编号范围不确定时多开一些空间没毛病但小数组导致越界是灾难性的。我一般习惯MAX_STATION开到比题面上限大10~20不留隐患。第六输出格式要严格按题目要求。有些题要求每个查询输出一行有些要求没有路径时输出-1还有些要求输出No way。格式错了就算答案对也白搭。第七建议把Dijkstra和BFS分别封装成独立函数不要揉在一块。因为当你需要先算换乘次数、再算最少站数时两个算法的逻辑容易互相干扰封装好了既能复用又能减少出错。公交系统这道题从难度上说算不上顶尖但从训练价值上说相当高。它逼着你认真思考如何把现实问题抽象成图而不是拿到题就套模板。如果你能把这道题用两种独立方案做出来并且把边界情况都测过一遍那你的图论基础就已经相当扎实了后面再遇到类似的状态图转化题基本就是同一套思路换个壳而已。