今天打卡到第六十三天图论部分正好进入一个承上启下的节点。卡码网KamaCoder这两道题——117. 软件构建和47. 参加科学大会一个是有向无环图的拓扑排序一个是带权图的最短路径可以说是把“图论里最实用的两类问题”一次性摆到了你面前。说它们实用是因为拓扑排序对应的是软件包依赖、编译顺序、任务调度这些每天都在发生的场景而Dijkstra迪杰斯特拉算法更是导航、网络路由、物流规划背后的常客。这篇博文就把这两道题的完整解法、推导过程和踩坑记录都整理出来代码用C写核心思路讲清楚让你看完能直接上手复现也能理解为什么这类题在面试和实际工程里反复出现。1. 为什么第六十三天要同时刷这两道题1.1 两道题在训练营中的定位代码随想录的图论章节安排是有讲究的。前面几天把图的存储方式邻接矩阵、邻接表、深度优先搜索、广度优先搜索都过了一遍第六十三天开始进入“图论应用题”的阶段。拓扑排序本质上是“依赖关系”的线性化而最短路径则是“代价优化”问题一个是先决条件的处理一个是全局最优的选择。软件构建这道题的题面很直白有N个文件编号从0到N-1文件之间有依赖关系比如文件A依赖文件B那就得先构建B再构建A。题目会给你一个依赖关系列表要求你输出一个合法的构建顺序如果存在循环依赖就输出空。这不就是现实中make、gradle、maven构建项目时干的事情吗编译系统拿到依赖图必须先拓扑排序才能决定谁能先编译。参加科学大会这道题题面可以理解为给定N个地点和M条单向路线每条路线有一个通行代价求从起点到终点的最小代价。如果不可达就返回-1。这个就是标准的最短路问题边上带权权值可以是时间、距离、金钱消耗中的任意一种。题解标准做法是Dijkstra算法因为训练营这个阶段还没有引入堆优化和SPFA所以用朴素O(V^2)版本完全够用。1.2 两道题背后隐含的经典场景刷题不能只背模板得知道模型是从哪来的。拓扑排序对应的现实问题除了软件构建还有课程表的先修课程安排比如选课系统里“要先学高数才能学线代”、数据库里外键约束的初始化顺序、甚至是包管理器里npm install的依赖解析。只要问题里有“谁必须先于谁完成”的描述第一反应就应该是拓扑排序。最短路径对应的场景就更多了。导航App里从A点到B点的最短驾车时间、快递配送的路径规划、网络协议中OSPF开放最短路径优先的路由计算底层跑的算法都离不开Dijkstra思想。区别只是工程上会加堆优化、用邻接表存储、甚至上A*搜索方向加速但核心的“松弛操作”思想是完全一致的。所以这两道题放在同一天刷训练的价值就在于你能从两个维度理解“图”这个数据结构——依赖维度和代价维度。依赖图关心的是次序代价值图关心的是权重。1.3 我对这道题组合的真实感受说实话初次刷这两题的时候我最直观的感受是“拓扑排序比最短路好理解得多”。拓扑排序逻辑起点很朴素入度为0的节点说明没有前置依赖可以直接处理处理完就把它指向的节点的入度减1再继续找下一个入度为0的节点。反复循环就能得到合法的线性顺序。而Dijkstra需要转换视角。朴素版本里你需要从起点出发每一轮从未访问过的节点里挑一个距离起点最近的节点作为“已确定最短路径”的节点然后去更新它相邻节点的距离。这个“每次选最近、再扩展更新”的思路第一次接触确实需要花点时间消化。我建议你刷完题后自己歪歪扭扭画一个5个点的带权有向图手动跑一遍整个流程比看十遍代码都管用。2. 软件构建与卡码网117题的完整拆解2.1 看题面之前先把“依赖关系”翻译成图117题的输入格式是第一行N表示文件数量第二行M表示依赖关系数量接下来M行每行给出s, t表示文件s依赖文件t也就是先构建t再构建s。很多初学者第一件事就栽在理解这个输入上到底谁指向谁我的建议是不要死记“s依赖t”这句话而是问自己一个问题我给哪个节点累加入度拓扑排序里我们常说的“入度”指的是有多少条边指向自己。文件s依赖文件t意味着t要先构建那么在依赖图上应该画一条从t指向s的边因为t是s的前置条件。于是s的入度要加1因为它多了一个前置依赖。邻接表的存储则是graph[t].push_back(s)表示t处理完之后可以去解锁s。这个方向一旦搞错后面全乱套。我自己第一次写的时候就是搞反了结果构建顺序怎么都不对。记住一句话依赖别人的人入度加一被依赖的人出边指向别人。用代码来表达就是vectorvectorint graph(n); vectorint inDegree(n, 0); for (int i 0; i m; i) { int s, t; cin s t; // s依赖t graph[t].push_back(s); inDegree[s]; }2.2 为什么用邻接表而不是邻接矩阵卡码网这道题的N上限并不算大你用邻接矩阵也能过。但从训练的角度来说我强烈建议你习惯用邻接表原因有三个。第一个原因是复杂度。邻接矩阵存储需要O(V^2)的空间遍历某个节点的所有邻居需要O(V)的时间。而邻接表存储只需要O(VE)的空间遍历邻居也只需要O(出边数量)的时间。图越稀疏邻接表的优势越明显。第二个原因是代码的可读性。graph[t][i]和for (int next : graph[t])两种写法后者一眼就能看出“从t出发能到达哪些点”逻辑上更贴合“解除依赖”这个动作。第三个原因是为后续更复杂的图算法做准备。Kruskal最小生成树、堆优化的Dijkstra、SPFAShortest Path Faster Algorithm、拓扑排序的队列实现这些全部天然适合邻接表。你从一开始就用邻接表写后面换算法不会觉得别扭。当然邻接矩阵也不是一无是处。如果题目需要频繁判断两个点之间是否有边或者图非常稠密边数接近V^2邻接矩阵的O(1)查询优势就会体现出来。所以选择存储方式的核心依据是图的稀疏程度和你要做的操作类型而不是无脑选某一种。2.3 拓扑排序的三个核心步骤拓扑排序的标准实现就是Kahn算法BFS思路整个过程可以拆成三步。第一步把所有入度为0的节点放入队列。为什么入度为0因为这些节点没有任何前置依赖它们就是可以直接开工的任务。初始队列里可能有多个节点它们之间的相对顺序不影响正确性。第二步循环遍历队列。每次取出队首节点把它存到结果数组中然后遍历它的所有出边邻居把邻居的入度减1。如果某个邻居的入度减到了0说明这个邻居的所有前置依赖都已经处理完了它现在可以入队了。第三步循环结束后检查结果数组的长度是否等于N。如果等于说明所有节点都能被处理不存在循环依赖如果小于N说明有环存在那些永远无法把入度减到0的节点就是环上的节点。有一个小细节值得注意这个算法处理的是“每个文件最多构建一次”的场景所以不需要visited数组。入度减到0本身就是“可以处理”的标记入队之后节点被取出来结果就被记录。如果你看到某些写法里还有额外的标记数组通常是为了应对更复杂的场景比如去重要求这道题不需要。2.4 完整题解代码与执行流程下面给出C完整实现这个是我在卡码网提交通过的版本#include iostream #include vector #include queue using namespace std; int main() { int n, m; while (cin n m) { vectorvectorint graph(n); vectorint inDegree(n, 0); for (int i 0; i m; i) { int s, t; cin s t; // s依赖t先构建t graph[t].push_back(s); inDegree[s]; } queueint que; for (int i 0; i n; i) { if (inDegree[i] 0) { que.push(i); } } vectorint result; result.reserve(n); while (!que.empty()) { int cur que.front(); que.pop(); result.push_back(cur); for (int next : graph[cur]) { inDegree[next]--; if (inDegree[next] 0) { que.push(next); } } } if (result.size() n) { for (int i 0; i result.size(); i) { if (i 0) cout ; cout result[i]; } cout endl; } else { cout 0 endl; } } return 0; }注意最外层有一个while (cin n m)因为卡码网的题目通常是多组测试用例输入有的同学忘记写这个循环只过一组数据就报错了。多组输入的习惯在ACM风格题目中一定要养成哪怕题目描述里没明说也建议用这种写法兜底。执行流程举个例子。假设N4M4依赖关系是文件1依赖文件0文件2依赖文件0文件3依赖文件1和文件2。翻译成图就是graph[0] [1, 2], graph[1] [3], graph[2] [3]inDegree [0, 1, 1, 2]。初始队列里面只有节点0因为只有它没有前置依赖。取出0把1和2的入度各减11和2的入度都变成0都入队。假设先取出1处理把3的入度从2减到1再取出2把3的入度从1减到03入队。最后取出3。得到一个合法的构建顺序0 1 2 3。如果先取出的是2再取出1结果就是0 2 1 3两种顺序都正确。2.5 循环依赖的判定与处理循环依赖是个非常经典的坑。假设有三个文件文件A依赖B文件B依赖C文件C依赖A这就构成了一个环。此时所有节点的入度都不是0初始队列为空结果数组为空result.size() ! n直接输出0代表无法构建。程序判断“有环”的本质是环上的节点永远不会把入度减到0因为环上没有任何一个节点可以“先被处理”。所以最终结果长度一定小于节点总数。这个方法判断有向环是非常可靠的而且不会多占用额外空间。在实际工程里构建系统检测到循环依赖通常会报一个错误甚至帮你把环上的节点链打印出来。不过在算法题阶段只需要输出0表示无法完成构建即可。如果你想输出具体的环需要在图上做DFS检测每个节点的状态那就是更深一层的问题了。3. 参加科学大会与Dijkstra最短路径3.1 什么样的输入暗示我们要用Dijkstra47题的输入结构是第一行N个场地、M条单向路线接下来M行每行给出三个数from, to, weight表示从from到to有一条路线通行代价为weight。起点默认为1号场地有的版本是0号要求输出从起点到终点N的最小总代价。如果在审题时捕捉到这几个关键词——单项关系、带权、求最短总代价基本可以锁定用Dijkstra。带权图的最短路径问题只有权重为正时才能用Dijkstra如果权重有负数就得用Bellman-Ford算法进行多次松弛操作或者用SPFA这些在训练营后面的章节会展开。这道题明确说了权值都是正整数所以用Dijkstra是安全的。3.2 朴素Dijkstra的核心思想贪婪的松弛过程朴素Dijkstra的过程可以用一句话概括从起点出发每次从未确定最短距离的节点中挑一个当前距离值最小的节点把它标记为“已确定”然后用这个节点去尝试更新它的所有邻居节点的距离。这个“每次挑最小”的行为就是贪婪策略。为什么这样做是正确的因为所有边权都是正数所以任何经过其他未确定节点绕到当前最小节点的路径都不可能比当前直接的距离值更小绕路只会增加总代价。这就是Dijkstra正确性的根本依据。如果用生活化的例子来类比你在大学食堂一楼想去三楼的某个窗口。已知一楼到二楼有楼梯二楼到三楼也有楼梯也可能有一楼直达三楼的电梯。你不知道电梯是否存在、速度多快于是你先把所有已知的“从一楼能直接到达的地方”记下时间然后选一个时间最短的地方先去看看到了那里再重新更新其他地点的最短时间。反复执行这个流程最终就能得到从一楼到所有地方的最短时间。朴素Dijkstra在每一轮找最小值时需要扫描整个未访问节点集合所以时间复杂度是O(V^2)。在这个数据范围内完全可行。3.3 朴素版本完整代码与推演先给出朴素Dijkstra的C实现#include iostream #include vector #include climits using namespace std; int main() { int n, m; while (cin n m) { vectorvectorint graph(n 1, vectorint(n 1, INT_MAX / 2)); for (int i 0; i m; i) { int from, to, weight; cin from to weight; graph[from][to] weight; // 单向边 } vectorint minDist(n 1, INT_MAX / 2); vectorbool visited(n 1, false); minDist[1] 0; for (int round 0; round n - 1; round) { int cur -1; int curMin INT_MAX / 2; for (int i 1; i n; i) { if (!visited[i] minDist[i] curMin) { curMin minDist[i]; cur i; } } if (cur -1) break; // 剩下的节点都不可达 visited[cur] true; for (int next 1; next n; next) { if (!visited[next] graph[cur][next] INT_MAX / 2) { minDist[next] min(minDist[next], minDist[cur] graph[cur][next]); } } } if (minDist[n] INT_MAX / 2) { cout -1 endl; } else { cout minDist[n] endl; } } return 0; }做几个细节解释。先解释为什么初始化矩阵和minDist都用INT_MAX / 2而不是INT_MAX。因为后面要执行minDist[cur] graph[cur][next]如果这两个值都是INT_MAX相加时会发生整数溢出变成负值代码的错误非常隐蔽。除以2是为了确保两个最大值相加仍小于INT_MAX同时又足够大能表示“无穷远”的概念。再解释为什么要从1到n存储节点而不是0到n-1。这个纯粹是因为卡码网的题目要求起点编号是1为了和输入对齐直接用n1长度的数组最方便免得下标换算把自己搞晕。每道题你都要先看好输入输出描述的编号规则不要盲目套模板。最后解释一下外层循环为什么最多跑n-1轮。因为起点自己的最短距离已经确定了剩下n-1个节点每一轮能确定一个节点的最终最短路径。即使有些节点不可达循环会在cur -1时提前退出不会浪费多余轮次。3.4 堆优化版本应该怎么写朴素版本在数据量大的时候不够用这时需要引入堆优化Dijkstra。堆优化版本的核心改动有两处第一处是用优先队列最小堆存储候选节点按距离值从小到大排序这样每次取出堆顶就能拿到距离最小的节点而不是扫描整个数组第二处是用邻接表存储图这样遍历邻居的时间会大大降低。堆优化版本的代码思路如下起点入队循环处理队列。每次取出队首节点距离值最小的节点如果该节点已经被访问过直接跳过否则标记已访问遍历它的所有邻接边执行松弛操作。如果某个邻居的最短距离被更新了就把它重新入队。这里有一个非常关键的代码细节优先队列里存的pairint, int第一个int是距离值第二个int是节点编号。因为默认的priority_queue是最大堆所以我们要声明为greater模式或者把距离值取负数放入。我偏爱用greater代码更直观。#include iostream #include vector #include queue #include climits using namespace std; int main() { int n, m; while (cin n m) { vectorvectorpairint, int graph(n 1); for (int i 0; i m; i) { int from, to, weight; cin from to weight; graph[from].push_back({to, weight}); } vectorint minDist(n 1, INT_MAX / 2); vectorbool visited(n 1, false); minDist[1] 0; priority_queuepairint, int, vectorpairint, int, greaterpairint, int pq; pq.push({0, 1}); while (!pq.empty()) { auto [d, cur] pq.top(); pq.pop(); if (visited[cur]) continue; visited[cur] true; for (auto edge : graph[cur]) { int next edge.first; int weight edge.second; if (!visited[next] minDist[cur] weight minDist[next]) { minDist[next] minDist[cur] weight; pq.push({minDist[next], next}); } } } if (minDist[n] INT_MAX / 2) { cout -1 endl; } else { cout minDist[n] endl; } } return 0; }注意看visited标记的判断非常重要。虽然优先队列保证了取出的节点距离是最小的但同一个节点可能因为多次更新而进入队列多次。如果不加visited判断就会重复处理同一个节点虽然结果仍正确但效率会下降。在堆优化版本里一旦一个节点被取出来就说明它的最短路径已经确定后续再被更新不可能更小所以可以直接跳过。3.5 Dijkstra为什么不能处理负权边这个问题面试官特别喜欢问你自己也要想透彻。Dijkstra的每一步都建立在“已经确定最短路径的节点即使绕路也不可能更短”的基础之上而这个基础依赖所有边权非负。如果存在负权边情况就变了。假设从A到B有一条边权为10的边从A到C有一条边权为5的边从C到B有一条边权为-5的边。那么现在从A到B最短的路是先经过C再经过B总代价是0比直接走10还要短。但是Dijkstra在第一轮选择时会先从A到C代价5确定C的最短路径为5然后第二轮取出B代价10确定B的最短路径为10。此时你永远不会用C更新B因为C已经被标记为已访问了。这样算出来的结果就是错的。所以看到负权边立刻换用Bellman-Ford。那道题虽然可能让你用Dijkstra就够但你需要具备判断“什么时候不能用什么算法”的能力。4. 刷题过程中的常见问题和排查技巧4.1 拓扑排序结果不唯一的分支处理有些同学做完拓扑排序后发现自己的输出和标准答案不一样就以为自己写错了其实很可能只是合法的不同次序而已。卡码网的判题系统通常会做特殊性判断只要你的输出是一个合法的拓扑序列就判对。什么情况下会出现多解初始入度为0的节点就有多个、或者多个节点的入度同时降到0时选择处理顺序的不同会直接导致输出顺序不同。这不是bug而是拓扑排序的天然性质。如果题目要求字典序最小你需要把普通的队列换成优先队列每次弹出编号最小的可处理节点。工程上构建系统为了保证构建结果可复现通常会选用固定的排序规则。4.2 优先队列的排序规则对比写到堆优化Dijkstra时很多新手容易犯一个经典的错误写成了把{cur, distance}放进优先队列然后发现结果不对。pair的默认排序规则是先比较第一个元素再比较第二个元素。所以如果你把节点编号放在第一个位置优先队列就会按节点编号排序而不是按距离排序整个算法就会退化成“按编号顺序一个个访问”完全失去Dijkstra的贪心特性。正确做法是把距离放在第一个位置节点编号放第二个位置。如果你觉得每次写greaterpairint, int比较烦可以使用using Node pairint, int;来给类型起别名或者干脆写一个自定义比较器这会减少很多笔误。4.3 多组输入导致的状态未清空问题卡码网这类OJ在线判题系统的一大特点就是多组测试数据。如果变量定义在while循环外面而你在处理完一组数据后没有重置数组下一组数据就会带着旧的状态运行结果必然出错。我在刷题时习惯把核心数据结构全部定义在while循环内部让每组测试用例都有全新的存储空间。这样虽然看起来有点浪费内存但对正确性的保证效果是立竿见影的。特别是vector这种容器每次循环重新构造的开销远远小于排查状态残留问题的时间成本。4.4 题目细节输出格式与编号起点很多卡在边界上的同学不是算法写错了而是没注意到起点的编号是1而不是0。如果题目要求输出“从1到N的最短路径”而你的循环从0开始遍历最终会漏掉起点。建议每次写题前先把输入输出范围抄在草稿纸上包括编号起点、是否有重边重边取最小值、是否有多组测试用例、不可达时输出什么。把这些边缘情况确认好再开始写算法。还有一个常见问题题目有可能存在重边也就是同一对from和to给了多条不同权重的路线。如果你用邻接矩阵存储直接执行graph[from][to] weight会把前面更小的权值覆盖掉吗不会覆盖吗要分情况。如果直接赋值后面大的权值就把前面小的权值覆盖了那求最短路就会出错。稳妥做法是graph[from][to] min(graph[from][to], weight)保留最小权值。虽然大部分案例数据不会出这种刁钻的输入但这个好习惯值得养成。5. 把算法延伸到真实世界5.1 软件构建中的拓扑排序与构建号回到标题里出现的热搜词有源医疗器械、独立软件、软件组件和固件的构建号。这个组合看起来很专业但本质上说的就是软件工程里的构建管理问题。大型医疗设备里往往包含独立软件比如控制台程序、软件组件比如图像处理模块和固件比如底层驱动它们之间有严格的依赖关系。先构建哪个、后构建哪个必须按拓扑顺序来。而构建号的意义就是给每一次构建打一个唯一的时间戳标识方便追溯是哪一次构建、哪个依赖版本、哪次提交引入了问题。算法题的软件构建是抽象模型真实的软件构建系统要复杂得多要考虑不同分支的版本差异、缓存机制、增量编译、跨平台差异但最底层的依赖解析逻辑依然是拓扑排序。你刷的每一道模板题都可能在某个具体产品的构建流水线里找到影子。这也是我在训练营反复强调“不要只满足于AC”的原因。把题面映射到工程场景知识才真正变成生产力。5.2 最短路径在导航与路由中的应用Dijkstra更不用说。导航软件里的路线规划、地图服务的驾车路线、物流调度系统的路径优化甚至OSPF路由协议都基于最短路径算法。你可以想象一个快递员要从配送中心出发去10个驿站送货求最短路径。直接跑Dijkstra能算出单点到各点的最短距离而如果要求“访问所有点并回到起点”的最短回路那就升级成了TSP旅行商问题难度完全不同。实际工程里的地图导航比算法题更复杂因为要处理实时路况边的权重随时间变化、多条候选路径、禁行区域这些都是在基础最短路算法之上做扩展。所以算法题的模板是地基地基不牢固上层建筑再花哨也会塌。我个人在实际使用中一直有个体会方案选型不要跟着模板走要跟着数据规模走。同样是Dijkstra数据量小的时候朴素版本半小时就能写完调通数据量大的时候老老实实上堆优化版。如果你在交作业或面试时为了秀技术明明N只有100还硬上优先队列反倒会让代码显得冗长。知道每种算法在什么条件下发挥最优性能比会背十种模板更有价值。最后再分享一个小技巧。做完117题之后如果你还有余力可以自己试着改造一下拓扑排序加一个result.size() n的判断后把环上的节点打印出来再做一版字典序最小的拓扑排序。做完47题之后可以自己转型成堆优化版再尝试处理负权边情况当然要把Dijkstra换成Bellman-Ford。把模板题吃透的最好方法就是给自己加戏用新的约束条件逼着自己理解本质。这样到训练营后期刷复杂题目时你会发现很多“新题”不过是旧模型的排列组合。卡码网这两道题都不难但它们是后续一切图论应用题的基石值得花时间好好打磨。 
长河君 · 2026/10/12 21:31:56 · 阅读 1.2k 拓扑排序与Dijkstra最短路径：图论两大核心算法C++实战解析
今天打卡到第六十三天图论部分正好进入一个承上启下的节点。卡码网KamaCoder这两道题——117. 软件构建和47. 参加科学大会一个是有向无环图的拓扑排序一个是带权图的最短路径可以说是把“图论里最实用的两类问题”一次性摆到了你面前。说它们实用是因为拓扑排序对应的是软件包依赖、编译顺序、任务调度这些每天都在发生的场景而Dijkstra迪杰斯特拉算法更是导航、网络路由、物流规划背后的常客。这篇博文就把这两道题的完整解法、推导过程和踩坑记录都整理出来代码用C写核心思路讲清楚让你看完能直接上手复现也能理解为什么这类题在面试和实际工程里反复出现。1. 为什么第六十三天要同时刷这两道题1.1 两道题在训练营中的定位代码随想录的图论章节安排是有讲究的。前面几天把图的存储方式邻接矩阵、邻接表、深度优先搜索、广度优先搜索都过了一遍第六十三天开始进入“图论应用题”的阶段。拓扑排序本质上是“依赖关系”的线性化而最短路径则是“代价优化”问题一个是先决条件的处理一个是全局最优的选择。软件构建这道题的题面很直白有N个文件编号从0到N-1文件之间有依赖关系比如文件A依赖文件B那就得先构建B再构建A。题目会给你一个依赖关系列表要求你输出一个合法的构建顺序如果存在循环依赖就输出空。这不就是现实中make、gradle、maven构建项目时干的事情吗编译系统拿到依赖图必须先拓扑排序才能决定谁能先编译。参加科学大会这道题题面可以理解为给定N个地点和M条单向路线每条路线有一个通行代价求从起点到终点的最小代价。如果不可达就返回-1。这个就是标准的最短路问题边上带权权值可以是时间、距离、金钱消耗中的任意一种。题解标准做法是Dijkstra算法因为训练营这个阶段还没有引入堆优化和SPFA所以用朴素O(V^2)版本完全够用。1.2 两道题背后隐含的经典场景刷题不能只背模板得知道模型是从哪来的。拓扑排序对应的现实问题除了软件构建还有课程表的先修课程安排比如选课系统里“要先学高数才能学线代”、数据库里外键约束的初始化顺序、甚至是包管理器里npm install的依赖解析。只要问题里有“谁必须先于谁完成”的描述第一反应就应该是拓扑排序。最短路径对应的场景就更多了。导航App里从A点到B点的最短驾车时间、快递配送的路径规划、网络协议中OSPF开放最短路径优先的路由计算底层跑的算法都离不开Dijkstra思想。区别只是工程上会加堆优化、用邻接表存储、甚至上A*搜索方向加速但核心的“松弛操作”思想是完全一致的。所以这两道题放在同一天刷训练的价值就在于你能从两个维度理解“图”这个数据结构——依赖维度和代价维度。依赖图关心的是次序代价值图关心的是权重。1.3 我对这道题组合的真实感受说实话初次刷这两题的时候我最直观的感受是“拓扑排序比最短路好理解得多”。拓扑排序逻辑起点很朴素入度为0的节点说明没有前置依赖可以直接处理处理完就把它指向的节点的入度减1再继续找下一个入度为0的节点。反复循环就能得到合法的线性顺序。而Dijkstra需要转换视角。朴素版本里你需要从起点出发每一轮从未访问过的节点里挑一个距离起点最近的节点作为“已确定最短路径”的节点然后去更新它相邻节点的距离。这个“每次选最近、再扩展更新”的思路第一次接触确实需要花点时间消化。我建议你刷完题后自己歪歪扭扭画一个5个点的带权有向图手动跑一遍整个流程比看十遍代码都管用。2. 软件构建与卡码网117题的完整拆解2.1 看题面之前先把“依赖关系”翻译成图117题的输入格式是第一行N表示文件数量第二行M表示依赖关系数量接下来M行每行给出s, t表示文件s依赖文件t也就是先构建t再构建s。很多初学者第一件事就栽在理解这个输入上到底谁指向谁我的建议是不要死记“s依赖t”这句话而是问自己一个问题我给哪个节点累加入度拓扑排序里我们常说的“入度”指的是有多少条边指向自己。文件s依赖文件t意味着t要先构建那么在依赖图上应该画一条从t指向s的边因为t是s的前置条件。于是s的入度要加1因为它多了一个前置依赖。邻接表的存储则是graph[t].push_back(s)表示t处理完之后可以去解锁s。这个方向一旦搞错后面全乱套。我自己第一次写的时候就是搞反了结果构建顺序怎么都不对。记住一句话依赖别人的人入度加一被依赖的人出边指向别人。用代码来表达就是vectorvectorint graph(n); vectorint inDegree(n, 0); for (int i 0; i m; i) { int s, t; cin s t; // s依赖t graph[t].push_back(s); inDegree[s]; }2.2 为什么用邻接表而不是邻接矩阵卡码网这道题的N上限并不算大你用邻接矩阵也能过。但从训练的角度来说我强烈建议你习惯用邻接表原因有三个。第一个原因是复杂度。邻接矩阵存储需要O(V^2)的空间遍历某个节点的所有邻居需要O(V)的时间。而邻接表存储只需要O(VE)的空间遍历邻居也只需要O(出边数量)的时间。图越稀疏邻接表的优势越明显。第二个原因是代码的可读性。graph[t][i]和for (int next : graph[t])两种写法后者一眼就能看出“从t出发能到达哪些点”逻辑上更贴合“解除依赖”这个动作。第三个原因是为后续更复杂的图算法做准备。Kruskal最小生成树、堆优化的Dijkstra、SPFAShortest Path Faster Algorithm、拓扑排序的队列实现这些全部天然适合邻接表。你从一开始就用邻接表写后面换算法不会觉得别扭。当然邻接矩阵也不是一无是处。如果题目需要频繁判断两个点之间是否有边或者图非常稠密边数接近V^2邻接矩阵的O(1)查询优势就会体现出来。所以选择存储方式的核心依据是图的稀疏程度和你要做的操作类型而不是无脑选某一种。2.3 拓扑排序的三个核心步骤拓扑排序的标准实现就是Kahn算法BFS思路整个过程可以拆成三步。第一步把所有入度为0的节点放入队列。为什么入度为0因为这些节点没有任何前置依赖它们就是可以直接开工的任务。初始队列里可能有多个节点它们之间的相对顺序不影响正确性。第二步循环遍历队列。每次取出队首节点把它存到结果数组中然后遍历它的所有出边邻居把邻居的入度减1。如果某个邻居的入度减到了0说明这个邻居的所有前置依赖都已经处理完了它现在可以入队了。第三步循环结束后检查结果数组的长度是否等于N。如果等于说明所有节点都能被处理不存在循环依赖如果小于N说明有环存在那些永远无法把入度减到0的节点就是环上的节点。有一个小细节值得注意这个算法处理的是“每个文件最多构建一次”的场景所以不需要visited数组。入度减到0本身就是“可以处理”的标记入队之后节点被取出来结果就被记录。如果你看到某些写法里还有额外的标记数组通常是为了应对更复杂的场景比如去重要求这道题不需要。2.4 完整题解代码与执行流程下面给出C完整实现这个是我在卡码网提交通过的版本#include iostream #include vector #include queue using namespace std; int main() { int n, m; while (cin n m) { vectorvectorint graph(n); vectorint inDegree(n, 0); for (int i 0; i m; i) { int s, t; cin s t; // s依赖t先构建t graph[t].push_back(s); inDegree[s]; } queueint que; for (int i 0; i n; i) { if (inDegree[i] 0) { que.push(i); } } vectorint result; result.reserve(n); while (!que.empty()) { int cur que.front(); que.pop(); result.push_back(cur); for (int next : graph[cur]) { inDegree[next]--; if (inDegree[next] 0) { que.push(next); } } } if (result.size() n) { for (int i 0; i result.size(); i) { if (i 0) cout ; cout result[i]; } cout endl; } else { cout 0 endl; } } return 0; }注意最外层有一个while (cin n m)因为卡码网的题目通常是多组测试用例输入有的同学忘记写这个循环只过一组数据就报错了。多组输入的习惯在ACM风格题目中一定要养成哪怕题目描述里没明说也建议用这种写法兜底。执行流程举个例子。假设N4M4依赖关系是文件1依赖文件0文件2依赖文件0文件3依赖文件1和文件2。翻译成图就是graph[0] [1, 2], graph[1] [3], graph[2] [3]inDegree [0, 1, 1, 2]。初始队列里面只有节点0因为只有它没有前置依赖。取出0把1和2的入度各减11和2的入度都变成0都入队。假设先取出1处理把3的入度从2减到1再取出2把3的入度从1减到03入队。最后取出3。得到一个合法的构建顺序0 1 2 3。如果先取出的是2再取出1结果就是0 2 1 3两种顺序都正确。2.5 循环依赖的判定与处理循环依赖是个非常经典的坑。假设有三个文件文件A依赖B文件B依赖C文件C依赖A这就构成了一个环。此时所有节点的入度都不是0初始队列为空结果数组为空result.size() ! n直接输出0代表无法构建。程序判断“有环”的本质是环上的节点永远不会把入度减到0因为环上没有任何一个节点可以“先被处理”。所以最终结果长度一定小于节点总数。这个方法判断有向环是非常可靠的而且不会多占用额外空间。在实际工程里构建系统检测到循环依赖通常会报一个错误甚至帮你把环上的节点链打印出来。不过在算法题阶段只需要输出0表示无法完成构建即可。如果你想输出具体的环需要在图上做DFS检测每个节点的状态那就是更深一层的问题了。3. 参加科学大会与Dijkstra最短路径3.1 什么样的输入暗示我们要用Dijkstra47题的输入结构是第一行N个场地、M条单向路线接下来M行每行给出三个数from, to, weight表示从from到to有一条路线通行代价为weight。起点默认为1号场地有的版本是0号要求输出从起点到终点N的最小总代价。如果在审题时捕捉到这几个关键词——单项关系、带权、求最短总代价基本可以锁定用Dijkstra。带权图的最短路径问题只有权重为正时才能用Dijkstra如果权重有负数就得用Bellman-Ford算法进行多次松弛操作或者用SPFA这些在训练营后面的章节会展开。这道题明确说了权值都是正整数所以用Dijkstra是安全的。3.2 朴素Dijkstra的核心思想贪婪的松弛过程朴素Dijkstra的过程可以用一句话概括从起点出发每次从未确定最短距离的节点中挑一个当前距离值最小的节点把它标记为“已确定”然后用这个节点去尝试更新它的所有邻居节点的距离。这个“每次挑最小”的行为就是贪婪策略。为什么这样做是正确的因为所有边权都是正数所以任何经过其他未确定节点绕到当前最小节点的路径都不可能比当前直接的距离值更小绕路只会增加总代价。这就是Dijkstra正确性的根本依据。如果用生活化的例子来类比你在大学食堂一楼想去三楼的某个窗口。已知一楼到二楼有楼梯二楼到三楼也有楼梯也可能有一楼直达三楼的电梯。你不知道电梯是否存在、速度多快于是你先把所有已知的“从一楼能直接到达的地方”记下时间然后选一个时间最短的地方先去看看到了那里再重新更新其他地点的最短时间。反复执行这个流程最终就能得到从一楼到所有地方的最短时间。朴素Dijkstra在每一轮找最小值时需要扫描整个未访问节点集合所以时间复杂度是O(V^2)。在这个数据范围内完全可行。3.3 朴素版本完整代码与推演先给出朴素Dijkstra的C实现#include iostream #include vector #include climits using namespace std; int main() { int n, m; while (cin n m) { vectorvectorint graph(n 1, vectorint(n 1, INT_MAX / 2)); for (int i 0; i m; i) { int from, to, weight; cin from to weight; graph[from][to] weight; // 单向边 } vectorint minDist(n 1, INT_MAX / 2); vectorbool visited(n 1, false); minDist[1] 0; for (int round 0; round n - 1; round) { int cur -1; int curMin INT_MAX / 2; for (int i 1; i n; i) { if (!visited[i] minDist[i] curMin) { curMin minDist[i]; cur i; } } if (cur -1) break; // 剩下的节点都不可达 visited[cur] true; for (int next 1; next n; next) { if (!visited[next] graph[cur][next] INT_MAX / 2) { minDist[next] min(minDist[next], minDist[cur] graph[cur][next]); } } } if (minDist[n] INT_MAX / 2) { cout -1 endl; } else { cout minDist[n] endl; } } return 0; }做几个细节解释。先解释为什么初始化矩阵和minDist都用INT_MAX / 2而不是INT_MAX。因为后面要执行minDist[cur] graph[cur][next]如果这两个值都是INT_MAX相加时会发生整数溢出变成负值代码的错误非常隐蔽。除以2是为了确保两个最大值相加仍小于INT_MAX同时又足够大能表示“无穷远”的概念。再解释为什么要从1到n存储节点而不是0到n-1。这个纯粹是因为卡码网的题目要求起点编号是1为了和输入对齐直接用n1长度的数组最方便免得下标换算把自己搞晕。每道题你都要先看好输入输出描述的编号规则不要盲目套模板。最后解释一下外层循环为什么最多跑n-1轮。因为起点自己的最短距离已经确定了剩下n-1个节点每一轮能确定一个节点的最终最短路径。即使有些节点不可达循环会在cur -1时提前退出不会浪费多余轮次。3.4 堆优化版本应该怎么写朴素版本在数据量大的时候不够用这时需要引入堆优化Dijkstra。堆优化版本的核心改动有两处第一处是用优先队列最小堆存储候选节点按距离值从小到大排序这样每次取出堆顶就能拿到距离最小的节点而不是扫描整个数组第二处是用邻接表存储图这样遍历邻居的时间会大大降低。堆优化版本的代码思路如下起点入队循环处理队列。每次取出队首节点距离值最小的节点如果该节点已经被访问过直接跳过否则标记已访问遍历它的所有邻接边执行松弛操作。如果某个邻居的最短距离被更新了就把它重新入队。这里有一个非常关键的代码细节优先队列里存的pairint, int第一个int是距离值第二个int是节点编号。因为默认的priority_queue是最大堆所以我们要声明为greater模式或者把距离值取负数放入。我偏爱用greater代码更直观。#include iostream #include vector #include queue #include climits using namespace std; int main() { int n, m; while (cin n m) { vectorvectorpairint, int graph(n 1); for (int i 0; i m; i) { int from, to, weight; cin from to weight; graph[from].push_back({to, weight}); } vectorint minDist(n 1, INT_MAX / 2); vectorbool visited(n 1, false); minDist[1] 0; priority_queuepairint, int, vectorpairint, int, greaterpairint, int pq; pq.push({0, 1}); while (!pq.empty()) { auto [d, cur] pq.top(); pq.pop(); if (visited[cur]) continue; visited[cur] true; for (auto edge : graph[cur]) { int next edge.first; int weight edge.second; if (!visited[next] minDist[cur] weight minDist[next]) { minDist[next] minDist[cur] weight; pq.push({minDist[next], next}); } } } if (minDist[n] INT_MAX / 2) { cout -1 endl; } else { cout minDist[n] endl; } } return 0; }注意看visited标记的判断非常重要。虽然优先队列保证了取出的节点距离是最小的但同一个节点可能因为多次更新而进入队列多次。如果不加visited判断就会重复处理同一个节点虽然结果仍正确但效率会下降。在堆优化版本里一旦一个节点被取出来就说明它的最短路径已经确定后续再被更新不可能更小所以可以直接跳过。3.5 Dijkstra为什么不能处理负权边这个问题面试官特别喜欢问你自己也要想透彻。Dijkstra的每一步都建立在“已经确定最短路径的节点即使绕路也不可能更短”的基础之上而这个基础依赖所有边权非负。如果存在负权边情况就变了。假设从A到B有一条边权为10的边从A到C有一条边权为5的边从C到B有一条边权为-5的边。那么现在从A到B最短的路是先经过C再经过B总代价是0比直接走10还要短。但是Dijkstra在第一轮选择时会先从A到C代价5确定C的最短路径为5然后第二轮取出B代价10确定B的最短路径为10。此时你永远不会用C更新B因为C已经被标记为已访问了。这样算出来的结果就是错的。所以看到负权边立刻换用Bellman-Ford。那道题虽然可能让你用Dijkstra就够但你需要具备判断“什么时候不能用什么算法”的能力。4. 刷题过程中的常见问题和排查技巧4.1 拓扑排序结果不唯一的分支处理有些同学做完拓扑排序后发现自己的输出和标准答案不一样就以为自己写错了其实很可能只是合法的不同次序而已。卡码网的判题系统通常会做特殊性判断只要你的输出是一个合法的拓扑序列就判对。什么情况下会出现多解初始入度为0的节点就有多个、或者多个节点的入度同时降到0时选择处理顺序的不同会直接导致输出顺序不同。这不是bug而是拓扑排序的天然性质。如果题目要求字典序最小你需要把普通的队列换成优先队列每次弹出编号最小的可处理节点。工程上构建系统为了保证构建结果可复现通常会选用固定的排序规则。4.2 优先队列的排序规则对比写到堆优化Dijkstra时很多新手容易犯一个经典的错误写成了把{cur, distance}放进优先队列然后发现结果不对。pair的默认排序规则是先比较第一个元素再比较第二个元素。所以如果你把节点编号放在第一个位置优先队列就会按节点编号排序而不是按距离排序整个算法就会退化成“按编号顺序一个个访问”完全失去Dijkstra的贪心特性。正确做法是把距离放在第一个位置节点编号放第二个位置。如果你觉得每次写greaterpairint, int比较烦可以使用using Node pairint, int;来给类型起别名或者干脆写一个自定义比较器这会减少很多笔误。4.3 多组输入导致的状态未清空问题卡码网这类OJ在线判题系统的一大特点就是多组测试数据。如果变量定义在while循环外面而你在处理完一组数据后没有重置数组下一组数据就会带着旧的状态运行结果必然出错。我在刷题时习惯把核心数据结构全部定义在while循环内部让每组测试用例都有全新的存储空间。这样虽然看起来有点浪费内存但对正确性的保证效果是立竿见影的。特别是vector这种容器每次循环重新构造的开销远远小于排查状态残留问题的时间成本。4.4 题目细节输出格式与编号起点很多卡在边界上的同学不是算法写错了而是没注意到起点的编号是1而不是0。如果题目要求输出“从1到N的最短路径”而你的循环从0开始遍历最终会漏掉起点。建议每次写题前先把输入输出范围抄在草稿纸上包括编号起点、是否有重边重边取最小值、是否有多组测试用例、不可达时输出什么。把这些边缘情况确认好再开始写算法。还有一个常见问题题目有可能存在重边也就是同一对from和to给了多条不同权重的路线。如果你用邻接矩阵存储直接执行graph[from][to] weight会把前面更小的权值覆盖掉吗不会覆盖吗要分情况。如果直接赋值后面大的权值就把前面小的权值覆盖了那求最短路就会出错。稳妥做法是graph[from][to] min(graph[from][to], weight)保留最小权值。虽然大部分案例数据不会出这种刁钻的输入但这个好习惯值得养成。5. 把算法延伸到真实世界5.1 软件构建中的拓扑排序与构建号回到标题里出现的热搜词有源医疗器械、独立软件、软件组件和固件的构建号。这个组合看起来很专业但本质上说的就是软件工程里的构建管理问题。大型医疗设备里往往包含独立软件比如控制台程序、软件组件比如图像处理模块和固件比如底层驱动它们之间有严格的依赖关系。先构建哪个、后构建哪个必须按拓扑顺序来。而构建号的意义就是给每一次构建打一个唯一的时间戳标识方便追溯是哪一次构建、哪个依赖版本、哪次提交引入了问题。算法题的软件构建是抽象模型真实的软件构建系统要复杂得多要考虑不同分支的版本差异、缓存机制、增量编译、跨平台差异但最底层的依赖解析逻辑依然是拓扑排序。你刷的每一道模板题都可能在某个具体产品的构建流水线里找到影子。这也是我在训练营反复强调“不要只满足于AC”的原因。把题面映射到工程场景知识才真正变成生产力。5.2 最短路径在导航与路由中的应用Dijkstra更不用说。导航软件里的路线规划、地图服务的驾车路线、物流调度系统的路径优化甚至OSPF路由协议都基于最短路径算法。你可以想象一个快递员要从配送中心出发去10个驿站送货求最短路径。直接跑Dijkstra能算出单点到各点的最短距离而如果要求“访问所有点并回到起点”的最短回路那就升级成了TSP旅行商问题难度完全不同。实际工程里的地图导航比算法题更复杂因为要处理实时路况边的权重随时间变化、多条候选路径、禁行区域这些都是在基础最短路算法之上做扩展。所以算法题的模板是地基地基不牢固上层建筑再花哨也会塌。我个人在实际使用中一直有个体会方案选型不要跟着模板走要跟着数据规模走。同样是Dijkstra数据量小的时候朴素版本半小时就能写完调通数据量大的时候老老实实上堆优化版。如果你在交作业或面试时为了秀技术明明N只有100还硬上优先队列反倒会让代码显得冗长。知道每种算法在什么条件下发挥最优性能比会背十种模板更有价值。最后再分享一个小技巧。做完117题之后如果你还有余力可以自己试着改造一下拓扑排序加一个result.size() n的判断后把环上的节点打印出来再做一版字典序最小的拓扑排序。做完47题之后可以自己转型成堆优化版再尝试处理负权边情况当然要把Dijkstra换成Bellman-Ford。把模板题吃透的最好方法就是给自己加戏用新的约束条件逼着自己理解本质。这样到训练营后期刷复杂题目时你会发现很多“新题”不过是旧模型的排列组合。卡码网这两道题都不难但它们是后续一切图论应用题的基石值得花时间好好打磨。