企业官网建设流程全解析

这段时间常在训练题里看到“公交系统”这类名字，第一眼觉得不就是个图论最短路，真要动手才发现，难点根本不在算法本身，而在怎么把一个现实中很自然的"换乘"问题，翻译成计算机能算的东西。我当初在这道题上卡了整整一个晚上，反复调整建图方式才跑通。这篇文章就把我对这类题目的完整思考和踩坑过程整理出来，从题面拆解、数据结构选型，到两套不同目标的算法实现和边界测试，一次性讲透。

1. 题面拆解：公交系统到底在考什么

1.1 看似是图论，其实考的是建图方式

先还原一下这道题常见的题面。给定若干条公交线路，每条线路按顺序经过一系列站点编号，再给若干个查询，每个查询给起点站和终点站，要求输出从起点到终点需要的最少换乘次数，或者最少经过的站点数（有的版本两个都问）。

很多人的第一反应是：站点就是图的节点，线路就是边，然后跑最短路。这个方向没错，但问题出在建图的粒度上。如果一条线路有十几个站，你直接把这条线路当成一条"从首站到尾站"的边，那就大错特错了——公交车只能沿着线路逐站走，不能跳站。你从第1站上车，不可能直接"坐"到第10站而不经过中间那些站点。所以建图时必须按照线路的相邻关系来连边，即第i站连第i+1站，而不是首尾相连。

这道题真正想考察的第一个能力就是"把文字描述转化成图模型"。同一条线路上的相邻站点之间有了一条边，意味着你可以坐着这条线从一站挪到相邻站；换乘则发生在两条线路共同经过的某个站点。把这些关系梳理清楚，后面的所有算法才有意义。

1.2 换乘次数和站点数，两种目标的本质差异

这道题最大的陷阱在于：同样一张公交网络，问"最少换乘次数"和"最少经过站点数"是两种完全不同的优化目标，建模方式截然不同。

• 最少换乘次数：你关心的是"我坐了几段不同的线路"，至于每段线路上坐了几站，根本无所谓。所以状态应该跟"线路"绑定，而不是跟"站点"绑定。
• 最少经过站点数：你关心的是"总共经过多少个站"，同一线路连续移动会产生累加的代价，所以每移动一站算一个代价，这天然对应加权图最短路。

我见过不少同学用一套代码去处理两个问题，结果换乘最少的时候绕了远路，或者站数最少但换乘了七八次。说到底，是因为没有意识到这两种目标背后的状态空间不一样。

下面两节分别给出两种建模方案和完整实现，先说最少换乘，再说最少站数。实际训练时建议两个版本分开写，逻辑更清晰，也利于调试。

2. 建图阶段：车站与线路的数据结构选型

2.1 邻接表还是邻接矩阵，关键看数据规模

程序训练题一般会限定数据范围，比如站点数不超过500，线路数不超过100，每条线路站点数不超过50。这个规模下，邻接矩阵和邻接表都能跑，但选择哪一个是会影响解题思路的。

如果只求最少换乘次数，一个非常经典的做法是在"线路编号"之间建图，而不是在"站点编号"之间建图。因为换乘的本质是"从一条线路换到另一条线路"，两条线路只要有共同站点，就能换乘，换乘代价记为1（或0，看具体定义）。这样一来：

• 图的节点是线路；
• 若线路A和线路B有公共站点，则A与B之间有一条边，权重为1（表示换乘一次）。

起点站和终点站的处理方式是：找出起点站属于哪些线路集合S，终点站属于哪些线路集合T，然后跑一个从"任一起始线路"到"任一目标线路"的最短路，最短路长度就是最少换乘次数。注意，如果起点站和终点站在同一条线路上，那答案直接是0次换乘，这是很多测试用例卡人的地方。

当使用线路图时，图的节点数是线路数，通常比站点数少一个数量级，用邻接矩阵存起来非常舒服。我习惯开一个vector数组记录每条线路经过的站点，同时开一个map<int, vector<int>> stationToLines记录每个站点被哪些线路经过，这样在建图时只需要遍历每对线路是否有共同站点就行。

2.2 把线路站序变成可检索的索引——线路到车站、车站到线路

具体来说，我会维护两份数据：

const int MAX_LINE = 105; const int MAX_STATION = 505; vector<int> lines[MAX_LINE]; // 每条线路依次经过的站点 vector<int> stationToLines[MAX_STATION]; // 每个站点属于哪些线路

读取输入时，对每条线路先把站点序列完整读入lines[i]，然后对每个站点station，往stationToLines[station]里加入线路编号i。要特别注意去重，因为同一条线路中站点不重复（题面一般保证），但多条线路可能共享站点，这在后面处理换乘时才是有效的换乘点。

有了这两份索引，判断两条线路能否换乘，只需要看它们是否有公共站点即可。最朴素的做法是直接二重循环对比，但更稳妥的方式是对每条线路的站点集合求交集。考虑到数据范围不大，我通常直接用一个布尔数组标记线路i上的所有站点，再遍历线路j的站点，只要有命中就说明两条线路连通。

vector<vector<int>> lineGraph(MAX_LINE, vector<int>(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？因为线路图中每条边的权重都是1，BFS天然就能求出无权图的最短路，时间复杂度O(V+E)，比Dijkstra更省，编码也更简单。

状态设计上，我让dist[i]表示从起始线路集合到线路i的最少换乘次数，初始状态把所有包含起点站的线路距离设为0。然后用队列做广度优先扩散：

int bfs(vector<vector<int>>& graph, int start, int target, vector<int>& startLines, vector<int>& targetLines) { queue<int> q; vector<int> 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_map<int, vector<int>>来存站到线路的映射，避免浪费内存和越界风险。

4. 算法方案二：最少站数的 Dijkstra 解法

4.1 加权图建模：同线相邻站权重为1

如果要算"最少经过站点数"，换乘次数就不够用了，得换一种建模方式。

这种情况下，我直接在站点之间建图。两个站点如果没有在任意一条线路上相邻，则没有边；如果相邻，则有一条权重为1的无向边（或者有向边，取决于题目是否允许双向坐车，绝大多数公交题默认双向可达，但个别题会声明单向，要仔细看题）。

为什么权重是1而不是"站数"？因为从站点A到相邻站点B，公交车只经过一站，所以把相邻站点间边的权重设为1。然后跑一次从起点站到终点站的单源最短路，得到的最短距离就是最少经过的站点数（严格来说，这里算的是经过的边数，也就是"坐了几站"，具体题目要求"经过的站点数"还是"经过的边数"要注意区分，通常边数加一才是站点数，但很多题把站数定义为坐过的站数，即边数，需要按题面来处理）。

注意，从这里就能看出和换乘问题的本质区别：这里你在同一条线路上连续移动，每次移动都会产生代价，所以不能只用线路作为节点。必须把站点作为节点，把"同一线路相邻站点"作为边。

4.2 用邻接表实现 Dijkstra

站点数如果不超过500，用邻接矩阵或者邻接表都行，但我推荐邻接表，因为实际代码里你还要根据线路动态建边，邻接表更方便。

const int INF = 0x3f3f3f3f; vector<pair<int, int>> adj[MAX_STATION]; void buildGraph(vector<int> 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}); // 根据题意决定是否双向 } } }

建好图后，跑标准Dijkstra：

int dijkstra(int start, int target) { vector<int> dist(MAX_STATION, INF); priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, 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 线路1：3个站：1->2->3 查询：从1到3 期望输出： 0（最少换乘次数），2（最少经过边数）

这一组如果输出换乘次数为1，说明你的初始入队逻辑有问题。

第二组：需要换乘一次。

输入： 2 3 1 2 3 4 5 6 1 4 查询：从1到4 线路1：1-2-3，线路2：4-5-6，无交点 期望输出： -1（无解）

如果这组输出一个数字而不是-1，说明你没判断无解。

第三组：两条线路在站点2交汇。

输入： 2 3 1 2 3 4 2 5 1 5 查询：从1到5 线路1：1-2-3，线路2：4-2-5 期望输出： 1（换乘1次），3（经过边数：1->2是1，2->4是2，4->5是3）

这组特别容易把最少站数算错，因为从1出发到5，可能你DFS时会找到一条"经过2再回到3再换乘"的绕路路径，导致算出的站数很大，但实际上走1->2->4->5就是最短路。

第四组：环线。

输入： 1 3 1 2 3 1 1 3 线路1：1->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作为未访问的判断条件，这其实是最简单也最不容易写错的方式：

vector<int> 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_map<int, vector<pair<int,int>>>做邻接表。

第三，优先队列的比较大小时，pair<int,int>默认先比较first再比较second，所以把距离放第一位、站点编号放第二位，配合greater<>就能得到小顶堆，不需要自定义比较函数。这个写法简洁且不容易错。

第四，如果有多组查询，尽量把图只建一次，然后每个查询单独跑最短路。不要在查询里重复建图，否则大数据的查询一多，时间就炸了。

第五，代码里宁可多开数组，不要用小数组。站点编号范围不确定时，多开一些空间没毛病，但小数组导致越界是灾难性的。我一般习惯MAX_STATION开到比题面上限大10~20，不留隐患。

第六，输出格式要严格按题目要求。有些题要求每个查询输出一行，有些要求没有路径时输出-1，还有些要求输出No way。格式错了，就算答案对也白搭。

第七，建议把Dijkstra和BFS分别封装成独立函数，不要揉在一块。因为当你需要先算换乘次数、再算最少站数时，两个算法的逻辑容易互相干扰，封装好了既能复用又能减少出错。

公交系统这道题，从难度上说算不上顶尖，但从训练价值上说相当高。它逼着你认真思考如何把现实问题抽象成图，而不是拿到题就套模板。如果你能把这道题用两种独立方案做出来，并且把边界情况都测过一遍，那你的图论基础就已经相当扎实了，后面再遇到类似的状态图转化题，基本就是同一套思路换个壳而已。