★ FEATURED ARTICLE 1. 题目解读这类“公交系统”到底在考什么1.1 经典题面与输入输出约定先把这个训练题的常见描述还原一下。题目一般会给你一个城市里若干条公交线路每条线路由若干个站名组成线路编号可能是数字也可能是字符串比如3 1: A B C D E 2: B F G 3: C G H I第一行是一个整数 n表示公交线路的数量接下来 n 行每行先给线路编号再给该线路经过的站名序列。然后是一个查询次数 m接下来 m 行每行两个站名要求输出从起点站到终点站需要乘坐的最少公交线路数以及换乘方案。不同训练平台给出的输入格式会有差异比如有的把线路编号和站名用空格分隔有的用“-”连接有的要求输出经过的站点列表有的只要求输出最少换乘数。但核心场景完全一致在只知道“某条线路经过哪些站”的情况下回答任意两个站点之间怎么乘车最省事。这个“最省事”在不同版本里可能指“换乘次数最少”也可能指“总站数最少”还有更狠的版本要求两个条件都要满足先换乘最少再总站数最少。这道题放在程序设计训练里非常典型因为它看起来像个应用题实际拆开却是三件事的叠加文本解析、数据结构设计、图算法。如果你在训练系统里看到这题的通过率不高不要意外它不是单纯的“读进来然后输出”而是需要你自己从零搭一套模型。1.2 隐藏考点数据建模、图论与边界处理先说数据建模。站点是字符串而图算法通常处理整数编号更高效所以第一件事是把每个站名映射成一个整数 ID。这个过程很简单但很多人会在这里踩坑站名可能重复出现在多条线路里映射表必须做去重否则同一个站会生成两个 ID后面的图就全乱了。再说图论。把公交线路抽象成图有两条路可以走。第一条是把“站”当节点两个站在同一条线路上相邻则连一条边然后求最短路径。这种方法适合算“最少站数”但换乘次数并不直接等于路径长度因为一条线路上连续坐很多站也只算坐了一趟车。第二条是把“线路”当节点两条线路如果有共同站点就认为它们之间可以换乘然后在这个“线路图”上做 BFS得到的就是最少换乘次数。实际训练题里这两种思路常常要结合使用。边界处理就更隐蔽了。起点站和终点站相同、起点和终点不在任何一条线路上、同一条线路内直达、两条线路有两个共同站点、线路是环线首尾站点相同、输入里存在空行或多余空格……这些情况如果你不在写代码之前列一张清单调试的时候会一个个蹦出来折磨你。1.3 明确训练目标你练的是工程拆分能力很多初学者拿到这题的第一反应是“直接模拟”也就是把每条线路当作一个字符串数组查询的时候双层循环找共同站点。如果数据量小比如 n ≤ 10、每线路站数 ≤ 20这种做法确实能出结果。但这题真正的训练价值恰恰在于你愿不愿意在动手写代码前把“模拟”升级成“模型”。从程序设计训练的角度看做完这题你应该掌握四件事如何用哈希表或有序表把字符串映射成整数从而把问题转化成纯数值运算如何根据题目语义选择正确的图模型而不是条件反射地套最短路模板如何用 BFS 求无权图的最短路径并且能记录路径、还原出具体的换乘方案如何系统地构造测试数据覆盖常见边界情况。如果你现在就准备打开编译器我建议你先别急着写代码。先把题面仔细读三遍搞清楚输入输出格式中每一个符号的含义再按下面的思路把模型搭出来你会发现后面写代码只是体力活。2. 数据结构选型与算法设计2.1 为什么不能直接用字符串数组硬怼先看一个最常见的错误设计定义一个二维字符数组char routes[100][100][20]第一维是线路编号第二维是站点序号第三维是站名。然后查询的时候遍历所有线路对于线路 A 上的每个站再遍历线路 B 上的每个站看有没有相同的。这个方案的致命问题有两个。第一空间浪费严重而且站名长度不固定短站名浪费得更多第二查询两个站点是否在“同一线路可达范围内”时你需要反复做字符串比较如果一条线路有 30 个站两条线路就要比较 900 次。当查询次数 m 也很大时整个程序会慢到让你怀疑人生。更关键的是这种设计没法回答“从 A 站到 B 站最少换乘几次”。因为线路之间的关系是“多对多”的A 站可能在 1 路和 5 路B 站在 3 路和 7 路你要知道 1 路和 3 路有没有共同站点5 路和 7 路有没有共同站点甚至 1 路和 7 路中间隔了几条线路。这个关系用二维数组存线路内部站点是无论如何也表达不清楚的。2.2 正确姿势编号映射 邻接表 线路关系图我个人的习惯做法分三层每一层都很简单但组合起来非常清晰第一层建立“站名 → 整数 ID”的映射。用一个结构体数组当字典遍历所有线路的每个站点如果站名没出现过就分配一个新 ID。这一步同时完成了站点去重后面所有算法都基于整数操作速度快、代码短。第二层记录“每条线路包含哪些站点”。最简单的是用一个二维数组vectorint lineStops[MAX_LINE]C 语言里用int lineStops[MAX_LINE][MAX_STOP]加一个行长度数组也行。这一层保留原始数据是后续建图的原料。第三层建立“线路之间能否换乘”的图。对任意两条线路如果它们有至少一个共同站点就认为这两条线路之间有一条无向边边权为 1 次换乘。在这个“线路图”上从起点站所属的线路出发到终点站所属的线路BFS 求出的最短距离加 1 就是最少乘坐线路数最短距离本身就是换乘次数。这里有个细节值得单独说一下为什么“加 1”因为如果起点站和终点站在同一线路你不需要换乘线路图里距离是 0但你需要乘坐 1 条线路。如果起点站在 1 路终点站在 3 路1 路和 2 路有共同站2 路和 3 路有共同站那么线路图距离是 21→2→3实际乘车次数是 3换乘次数是 2。这个换算关系一定要在写注释的时候写清楚不然过几天自己都容易绕晕。2.3 最少换乘BFS不是 Dijkstra很多人一看“最少换乘”条件反射就上了 Dijkstra。没必要因为换乘次数最少这个问题每条边的权重都是 1线路图是一个无权图BFS 天然就是最短路算法而且复杂度是 O(VE)比 Dijkstra 的 O((VE)logV) 更快代码也更短。BFS 的过程本质上就是“我从起点线路出发每次坐一趟车能到达哪些线路”。初始时把所有包含起点站的线路入队距离记为 0。然后逐层扩展如果当前线路与某条新线路有共同站点并且新线路还没访问过就把它入队距离加 1。直到队列中出现包含终点站的线路这个时候的距离就是最少换乘次数。很多人会问如果起点站本身就在多条线路上要不要全部入队答案是全部入队因为它们都是“起点”只不过你还没决定坐哪一路。只要有一条线路能最快到终点BFS 就会先找到它。那么怎么还原换乘方案通常需要记录每个线路节点的前驱prevLine。BFS 结束后从终点所在线路往回找就能得到一条线路序列比如 2 → 5 → 9。然后你要输出每一个换乘点的站名2 路和 5 路的共同站点、5 路和 9 路的共同站点。如果共同站点有多个一般取第一个或按输入顺序最小的那个具体看题目要求。2.4 如果题目要求“总站数最少”再叠加 Dijkstra有的训练题是升级版要求“换乘次数最少的前提下总站数也最少”。这时候单纯 BFS 就不够用了因为换乘次数相同的两条方案可能一个坐 3 站就到另一个要绕 8 站。我的处理办法是先跑一遍 BFS 算出最少换乘次数minTransfers然后在这个限制下求总站数最少。具体做法可以构造一个新图节点仍然是“某个站的某个站位”但边的含义更丰富——在同一线路上相邻的站之间边权为 1坐一站在不同线路的同一物理站点之间边权为 0换乘。然后在这个图上跑 Dijkstra限制条件“换乘次数不超过 minTransfers”可以通过维护二元组(距离, 换乘次数)来实现。不过说实话训练题里这种升级版本比较少见多数版本停留在“最少换乘次数”或者“最少站数”二者选其一。遇到升级版你再叠加 Dijkstra基础版先把 BFS 玩明白代码也能复用一大半。3. 核心代码落地从建图到查询的一步步实现3.1 预处理站点编号与线路站点表我用 C 语言来写因为程序设计训练最常见的环境就是 C 或 C。如果你用的是 Python思路完全一样只是容器不同。首先要定义一个字典。C 语言没有现成的哈希表我一般用一个结构体数组加线性查找。数据量不大时线性查找完全够用#include stdio.h #include string.h #define MAX_STATION 1000 #define MAX_LINE 100 #define MAX_STOP_PER_LINE 100 typedef struct { char name[32]; } Station; Station stations[MAX_STATION]; int stationCnt 0; int getStationId(char *name) { for (int i 0; i stationCnt; i) { if (strcmp(stations[i].name, name) 0) { return i; } } strcpy(stations[stationCnt].name, name); return stationCnt; }这个实现虽然简单但它保证了同一个站名永远对应同一个 ID。如果你担心查找速度可以把线性查找换成哈希表不过训练题的数据规模通常不会逼你优化到那个程度。接下来存线路数据int lineStops[MAX_LINE][MAX_STOP_PER_LINE]; // 每条线路经过的站点 ID int lineLen[MAX_LINE]; // 每条线路的站点数 int lineCnt 0;读入的时候每行先读线路编号再循环读站名直到换行。这里有个常见的坑scanf 遇到空格会停而站名之间就是用空格分隔的所以不要用%s直接读一整行。更稳妥的读法是用fgets读整行然后用strtok按空格拆或者先读一个换行符再用scanf(%s)逐个读站名直到读到换行为止。我倾向于fgets strtok因为换行符处理更可控。char line[500]; fgets(line, sizeof(line), stdin); char *token strtok(line, \n); while (token ! NULL) { int id getStationId(token); lineStops[lineCnt][lineLen[lineCnt]] id; token strtok(NULL, \n); } lineCnt;3.2 建“线路关系图”这是全题最重要的一个环节。我要建立一个二维邻接矩阵或邻接表表示两条线路是否可以通过某个站点换乘。判断方法很朴素遍历任意两条线路的所有站点看有没有交集。复杂度是 O(L² × S²)其中 L 是线路数S 是每线路最大站数对训练题规模完全够用。更高效的做法是把“站点 → 线路”的反向索引先建出来遍历每条线路的每个站点给站点 ID 对应的线路列表里加入当前线路编号。然后对任意两条线路如果它们都出现在同一个站点的线路列表里就说明有共同站点。这个做法实际写起来更自然也方便后面输出换乘站名。我常用邻接表int graph[MAX_LINE][MAX_LINE]; // 0 表示不能换乘1 表示可以 int graphEdgeCnt[MAX_LINE]; void buildGraph() { for (int stopId 0; stopId stationCnt; stopId) { // 找出所有经过该站点的线路 int linesAtStop[MAX_LINE]; int cnt 0; for (int i 0; i lineCnt; i) { for (int j 0; j lineLen[i]; j) { if (lineStops[i][j] stopId) { linesAtStop[cnt] i; break; } } } // 这些线路两两之间都能换乘 for (int i 0; i cnt; i) { for (int j i 1; j cnt; j) { int a linesAtStop[i], b linesAtStop[j]; if (graph[a][b] 0) { graph[a][b] graph[b][a] 1; graphEdgeCnt[a]; graphEdgeCnt[b]; } } } } }要注意的是同一站点有多条线路时不能让重复的线路对反复计数所以加了一个if (graph[a][b] 0)的判断避免后续 BFS 出现重复边。3.3 查询与 BFS 搜索一次查询给定起点站名和终点站名。第一步先把字符串转成站点 ID然后找出所有包含起点站的线路存入startLines[]所有包含终点站的线路存入endLines[]。接下来在“线路图”上 BFSint bfs(int startLine, int targetLineSet[], int targetCnt) { int queue[MAX_LINE], head 0, tail 0; int dist[MAX_LINE], prev[MAX_LINE], inQueue[MAX_LINE]; memset(dist, -1, sizeof(dist)); memset(prev, -1, sizeof(prev)); memset(inQueue, 0, sizeof(inQueue)); queue[tail] startLine; dist[startLine] 0; inQueue[startLine] 1; int targetLine -1; while (head tail) { int cur queue[head]; for (int i 0; i targetCnt; i) { if (cur targetLineSet[i]) { targetLine cur; break; } } if (targetLine ! -1) break; for (int nxt 0; nxt lineCnt; nxt) { if (graph[cur][nxt] !inQueue[nxt]) { queue[tail] nxt; dist[nxt] dist[cur] 1; prev[nxt] cur; inQueue[nxt] 1; } } } if (targetLine -1) return -1; // 不可达 // 从 targetLine 回溯 prev得到完整线路序列 int path[MAX_LINE], pathLen 0; for (int v targetLine; v ! -1; v prev[v]) { path[pathLen] v; } // 实际输出时需要逆序并找到换乘站点 return targetLine -1 ? -1 : dist[targetLine]; }注意这里有个微妙的地方起点站可能同时属于多条线路BFS 应该从所有startLines同时开始而不是只选一条。简单处理方式是设置一个虚拟起点它到所有startLines的距离都为 0或者把这些线路都先入队再统一 BFS。我通常用后者代码改动最小。如果 BFS 返回 -1说明这两个站之间无法通过现有公交线路到达输出时要明确提示“无可用路线”。很多训练题会有专门的输出规则比如no answer或者中文提示一定要先看清题面。3.4 换乘点与线路序列的输出BFS 只告诉我们“最少换乘几次”但训练题一般还要求输出具体换乘方案。回溯之后得到的是线路编号序列比如 [2, 5, 9]你需要输出这样的信息从 A 站出发乘坐 2 路 在 X 站换乘 5 路 在 Y 站换乘 9 路 到达 B 站X 站是 2 路和 5 路的第一个共同站点Y 站是 5 路和 9 路的第一个共同站点。这个“第一个共同站点”的选择题面可能有规定没有规定就自己定一个规则并保持一致比如取这两条线路上共同站点中站点 ID 最小的或者取在线路顺序中最靠前的。还有一个情况起点站和终点站在同一条线路。这时候不需要换乘直接输出“乘坐某路从 A 到 B”。注意如果起点站同时出现在多条线路上到底选哪条线路直答没有题面约束时选第一条即可。但要留意同一条线路里 A 和 B 出现的先后顺序方向不对可能需要反向乘坐。我把输出做成一个单独的函数这样查询逻辑和输出逻辑解耦改格式的时候不用动核心算法。4. 边界条件与测试用例设计4.1 边界条件清单这个题目的坑绝大多数不在算法本身而在边界条件。以下是我整理的一份清单强烈建议写代码前先过一遍起点站和终点站是同一个站。答案应该是 0 条线路还是 1 条线路不同题面定义不同通常我按“已经到达”处理但你要确认题面有没有特殊要求。起点站或终点站不存在于任何线路中。直接返回不可达不要试图在图上找它否则数组访问会越界。线路只有 1 条且站名全部不同起点终点都在线上。应输出直达。两条线路有多个共同站点。BFS 只关心“能否换乘”但输出时选哪个站要有明确规则。环线线路比如 1: A B C A首尾相同。处理时不要重复计数通常去重处理否则建图时同一个线路自己连自己会干扰判断。空线路或非法输入。严格来说训练题不会给空线路但为了程序健壮性解析时要注意空行。站点名包含数字或下划线比如Station_1。不要假设站名只由字母组成。线路编号不是从 1 开始连续编号。题目可能给 1、2、4、8你必须自己建立线路编号与数组下标的映射。4.2 测试用例速查表我实际调试时用的测试数据大概长这样用例输入要点输出预期基础直达仅 1 条线路A 和 B 都在上面直接乘坐换乘 0 次一次换乘1 路经过 A C2 路经过 C B换乘 1 次换乘点为 C两次换乘三条线路链式相连换乘 2 次同站多线A 站在 1、2、3 路都出现BFS 应选路径最短的那个出发点重复共同站1 路 A C D2 路 C D B换乘点输出规则要一致不可达两个站分属两个互不相通的子图返回无解起点终点相同A 到 A按题面要求输出大环线一条线路绕一整圈不会死循环BFS 深度有限我建议你把每个用例都写成独立的输入文件跑完直接对比输出。如果训练平台支持甚至可以把这些用例做成脚本批量验证这样每次改动后都能快速回归。4.3 常见运行时问题与排查技巧问题一BFS 结果总是多 1 或少 1。这是最经典的错误。原因是对“换乘次数”和“乘坐线路数”的换算没搞清。记住换乘次数 线路序列长度 - 1。你回溯得到的线路序列是 [2, 5, 9]就代表你坐了三趟车换乘了两次BFS 的距离是 2输出乘车线路数是 3。调试的时候在 BFS 返回处加一行临时输出看看dist到底是多少再对照手推结果。问题二栈溢出。如果你用递归写 DFS 来找路径线路数量稍微多一点就会爆栈。建议一律用队列 BFSC 语言的数组队列不涉及递归不会出现这个问题。如果真要用递归也请把递归深度控制在 50 以内。问题三换乘站输出错误。很多时候 BFS 得到的线路序列是对的但输出换乘站时取了错误的共同站点。记住换乘站的选取应该基于“这两条线路第一次出现交集的站”而不是全局第一个共同站。我在输出函数里会额外判断共同站点必须同时出现在两条线路中而且尽量选输入顺序靠前的这样人工核对时最直观。问题四字符串比较忽略大小写或尾部换行。用scanf(%s)读进来的站名一般没有问题但如果用了fgets一定要把末尾换行符去掉否则strcmp(A\n, A)永远不相等查半天发现是换行符的问题。5. 我实际带队做题的几点体会这题我见过无数人写通过率高的版本往往不是算法最漂亮的而是注释最清楚的。原因很简单这道题的代码量不大但查错成本很高如果你在bfs函数里不写注释说明“dist 表示换乘次数”过两天回来看保准要重新推一遍。还有一个建议先写一个最朴素的版本用二维数组存线路关系不加任何优化跑通所有样例。然后再去想要不要用邻接表优化要不要做反向索引。这个顺序能让你的思路一直清晰不会被细节淹没。等第二次写的时候你会发现邻接表版本其实代码量差不多但扩展性好很多。最后如果你在训练系统里提交后出现 Wrong Answer不要急着改代码先构造一个极简用例比如 2 条线路、3 个站点手推一遍再运行。大部分问题都是“输出格式多了一个空格”或者“换乘次数边界没算对”这种小坑看题面比改代码更有效。
阅读完成 · 觉得有帮助？
