今天是第50天我的算法训练打卡正式走到了图论part2。说实话走到这里的人已经不多了——前49天里数组、链表、哈希、二叉树、回溯、贪心、动态规划全都过了一遍刷题群里和我同期出发的人大概只剩下三分之一。图论这个专题特别有意思part1和part2的分界感非常强part1还在学怎么“看图”——存图、遍历、数连通块岛屿问题刷到头也就是DFS/BFS换着花样套模板到了part2问题开始从“图里有什么”变成“图上的最优决策是什么”最短路径、最小生成树、拓扑排序、并查集每一块拎出来都是新世界。今天这篇就把我进入图论part2之后的学习路线、核心算法复盘和踩坑记录整理一遍给同样卡在这个阶段的人一些参考。1. 从part1到part2day 50这道分水岭把我从“看图”推向“算图”1.1 前49天的路线是怎么安排的我的打卡不是瞎打前49天基本按这个节奏来的day 1-8数组、链表、哈希表、双指针。这一阶段的核心是“数据和指针的掌控力”后面很多图论模板都要依赖这些基本功。day 9-16栈、队列、二叉树基础。树的遍历和递归思维对图论part1帮助很大图的DFS/BFS本质上就是树的遍历的推广。day 17-24二叉树进阶、回溯。回溯的“路径记录”和“撤销操作”对图的路径枚举题很有用。day 25-32贪心、基础动态规划。这段很痛但给图论part2打了一针强心剂——后面学Dijkstra、Prim都会用到“局部最优证明全局最优”的思维方式。day 33-41动态规划进阶、前缀和、差分。day 42-49图论part1包括邻接矩阵和邻接表、DFS/BFS模板、岛屿问题、连通分量、BFS最短路。这个排布有它的道理需要强记忆和强递归的放在前面需要“证明直觉”的放在后面图论刚好卡在中间。现在回头看前面那些数组、栈、回溯的底子在图论里全都用得上——至少我被递归调用栈害过的时候第一反应是回去翻回溯模板而不是对着图发呆。1.2 图论part1到底学了什么part1的核心其实就是“遍历”。不管是用邻接矩阵还是邻接表本质都是把图结构存下来然后用DFS或BFS走一遍。刷到后面你会发现part1大部分题几乎是模板题无向图连通分量DFS/BFS每次把整个连通块染色。岛屿计数就是二维网格上的连通分量。水淹/填色DFS里顺手统计面积或周长。迷宫最短路BFS层数就是最短步数因为BFS天然按距离递增扩展。到了part1后期我对DFS/BFS的熟练度确实上来了但说实话这种熟练只停留在“会套模板”的层面。真正把我按在地上摩擦的是进入part2之后。原因是part2的题目没法靠背一个模板就解决你至少得知道“为什么这个算法是对的”“什么情况不能用它”。1.3 part2的分界感体现在哪part2不再是“走过去看看”而是“走过去并且要最优”。同样是图上搜索part1只看连通性part2要算权值同样是路径part1只有“有没有路”part2要问“哪条路最短”。这种从“存在性”到“最优性”的转变意味着我之前那一套“无脑套模板”的打法直接失效。举个例子part1里从1到nDFS能搜到场就结束了而part2里如果边有权重就得考虑“要不要绕路”“绕路会不会更短”“负权边能不能走”。这类问题更接近现实决策根本不是背模板能搞定的必须把算法原理吃透。这也是为什么我从这天开始每天晚上不再急着刷新题而是花时间重新推导当天算法的正确性。2. 最短路径起手式Dijkstra以及它身后的坑2.1 为什么所有教材都从Dijkstra开始Dijkstra是单源最短路里最经典也最好理解的一个从起点出发维护每个节点当前已知的最短距离每次从还没确定结果的点里挑一个距离最小的用它的所有出边去更新邻居然后把这个点标记为“已确定”。它之所以成立依赖一个非常强的前提所有边权非负。在这个前提下每当某个点被当作“当前距离最小”弹出时任何还没有找到的路径都不可能让它变得更小——因为所有边权都不小于0绕路只会让距离变大或持平不可能把之前的结果优化掉。我自己的理解方式是把它当成一场选秀每一轮从候选人里挑综合评分最高的直接晋级后面只要有人继续打分分数只会更高或不变所以先晋级的不会吃亏。如果存在负分评委情况就完全变了一个本来晋级的选手可能被后面某个负分项拉下水。负权边就是那个负分评委。2.2 朴素版为什么不够用朴素版Dijkstra每次要找“距离最小的未确定节点”这个扫描过程要O(V)整体复杂度O(V^2)。点数少的时候无所谓但图论题动辄上万节点再叠加超过十万条边这个复杂度就明显扛不住了。所以真正常用的是优先队列版本。核心思路是用一个小顶堆维护“当前距离最小的点”弹出时顺便处理所有出边复杂度降到O((EV)logV)。下面是我手写的模板C风格但思路所有语言通用// dist[v] 表示起点到 v 的最短距离初始为 INF // g[u] 存 (to, weight) priority_queuepairlong long,int, vectorpairlong long,int, greater pq; pq.push({0, start}); while (!pq.empty()) { auto [d, u] pq.top(); pq.pop(); if (d ! dist[u]) continue; // 关键跳过过期状态 for (auto [v, w] : g[u]) { if (dist[v] dist[u] w) { dist[v] dist[u] w; pq.push({dist[v], v}); } } }注意一个容易忽略的点优先队列里存的是状态同一个节点可能因为多次松弛而被入队好几遍。那行if (d ! dist[u]) continue;就是用来丢弃旧状态的没有它程序也能跑但队列里会积压大量无效元素复杂度直接退化。2.3 负权边与Dijkstra的失效现场负权边是Dijkstra的克星。一个最简单的反例三个点A、B、CA到B权值是3A到C权值是2C到B权值是-4。从A出发Dijkstra会先把距离为3的B“钉死”成答案但真实的A到B最短路其实是A-C-B 2 (-4) -2比3还小5。问题就出在“钉死”这个操作上Dijkstra的贪心假设了每次选出的最小距离不可能再被更新负权边直接推翻了这一条。所以遇到负权边但无负环的图要改用Bellman-Ford或SPFA如果存在负环那最短路本身就不存在。做题时务必先看清楚权值范围约束别一上来就写Dijkstra。2.4 我实际写下来觉得最重要的三件事距离类型统一用long long。尤其是“花费”“成本”这类累加型题目两个1e9级别的数加起来就可能超过int上限再用int存dist松弛判断直接出错。优先队列里pair的first放距离、second放节点。C的pair默认按first排序这么写刚好借助语言特性省掉自定义比较器。Java里如果写lambda也要明确比较的是dist而不是节点编号。INF不要设成int的最大值否则dist[u]w一算就溢出成负数整个松弛判断全会崩。我习惯用const long long INF 4e18;所有距离变量统一long long。提示如果你在本地测试Dijkstra建议写一个BFS暴力版跑随机小图把结果对拍。最短路径的算法题最容易出现“样例过了但WA到哭”的情况对拍是排查最快的路子。3. 最小生成树的两个流派Kruskal的并查集与Prim的贪心3.1 最小生成树到底要解决什么一个很生活化的问题在若干个点之间铺路要求所有点连通且总造价最低这就是最小生成树。注意它和最短路的区别最短路关心“从一个点到另一个点”最小生成树关心“让整张图连通且总权最小”。所以一棵生成树里可能包含一些长度很大的边只要它们能连接那些孤立部分它就是合理的。判断是否理解到位有一个小技巧在一个连通无向图里最小生成树一定存在但不一定唯一。如果所有边权都不相同那最小生成树是唯一的如果存在相同权值的边就可能发生“替换”而不影响总权值。这个判断在有些题目里会直接给你设坑。3.2 Kruskal从小到大挑边并查集管环Kruskal的做法很直白把所有边按权值从小到大排序然后逐个尝试。如果一条边的两个端点当前不在同一个连通块就把它选入生成树并union两个端点。这里的核心就是“并查集判环”两个点已经连通再加一条边必然成环不能要。为什么这个贪心是对的可以用“切割性质”来理解任意把点集切成两块横跨切割的所有边里最便宜的那条一定属于某个最小生成树。Kruskal每次加入的边其实是当前状态下最优的“跨切割边”。写出来大概长这样struct Edge { int u, v, w; }; sort(edges.begin(), edges.end(), [](auto a, auto b){ return a.w b.w; }); int cnt 0; long long sum 0; for (auto e : edges) { int ru find(e.u), rv find(e.v); if (ru ! rv) { parent[ru] rv; sum e.w; cnt; if (cnt n - 1) break; } } // cnt ! n - 1 说明原图不连通最小生成树不存在一个很容易出错的点排序比较器里如果写return a.w b.w;你得到的就是权值从大到小的顺序那整个逻辑就反了造出的全是当前最贵的边。这种错很难一眼看出来因为样例数据可能碰巧也能跑通一部分。3.3 Prim从点出发向外长成一棵树Prim的思路和Dijkstra长得非常像区别只有一个Dijkstra维护的是“到起点的距离”Prim维护的是“到已选集合的距离”。每次找一个集合外距离最小的点加入集合并用它更新其他集合外点到集合的距离。邻接矩阵版的Prim特别适合稠密图复杂度O(V^2)代码也短// g[i][j] 存边权dist[v] 表示 v 到已选集合的最小距离 dist[1] 0; for (int i 1; i n; i) { int u -1; for (int v 1; v n; v) if (!vis[v] (u -1 || dist[v] dist[u])) u v; vis[u] true; ans dist[u]; for (int v 1; v n; v) if (!vis[v] g[u][v] dist[v]) dist[v] g[u][v]; }这里有个细节因为vis会标记已经选过的点所以更新dist时只要关心未选集合内的点即可。如果你不小心把已选点的dist也更新了不影响答案但在调试时容易造成困惑。3.4 到底选哪个我的判断标准维度KruskalPrim邻接矩阵版核心依赖排序并查集贪心数组时间复杂度O(E logE)O(V^2)适合场景稀疏图、边数少稠密图、点数少代码量短但依赖并查集更短无额外结构易错点排序方向、并查集初始化起点dist没置0、vis漏标记我的建议是先学Kruskal因为并查集本身是图论part2的基础设施学会一遍同时练了两个核心技能。再学Prim因为理解了Prim的“到集合的距离”之后后面理解动态规划状态维护会更有直觉。做题时两者都能过的优先用自己最熟的那套但至少把另一套思路想明白因为部分题只适合其中一种。4. 并查集图论part2里被低估的基建4.1 并查集不是“图论专属”但它撑起了图论并查集维护的是集合的合并与查询基础操作就三个init每个人先自成一派、find找某个元素所在集合的根、union合并两个集合。图论里的高频场景是判断连通、维护连通块个数、配合Kruskal做最小生成树。用一句话理解它它像班级里查询“两个人是不是同一寝室的”通过在不断合并宿舍的过程中维护这个关系。如果两个人已经在同一间宿舍再强行合并就会产生冗余这正好对应图论里“加边成环”的判定。4.2 路径压缩和按秩合并的原理两个优化非常关键路径压缩find的时候把沿途节点的父指针直接指向根避免每次查询都向上爬好几层。按秩合并union的时候把深度小的树挂到深度大的树下面防止树长成一条链。两个优化一起写单次操作均摊复杂度几乎就是O(1)。官方说法是反阿克曼函数实战里你完全不用关心那个常数放心用。代码也极短int find(int x) { return parent[x] x ? x : parent[x] find(parent[x]); } void merge(int a, int b) { int ra find(a), rb find(b); if (ra ! rb) { if (rank[ra] rank[rb]) swap(ra, rb); parent[rb] ra; if (rank[ra] rank[rb]) rank[ra]; } }这两个优化缺一不可吗不是。只做路径压缩均摊已经很好但只做按秩合并没有路径压缩一些持续查询的题还是会卡。我的建议是都写反正就多两行。4.3 实战案例动态加边求连通块数量一个很经典的模型n个点初始互相独立依次加入m条无向边问每加一条边后图中还有多少个连通块。做法是并查集边加边维护连通块数初始为n每成功union一次减少1。复杂度几乎就是O(m)比每次重新DFS一遍优雅太多。这个模型在最小生成树、动态连通题里反复出现值得当成模板刻在脑子里。我记得第一次做这类题时连“连通块数量应该初始化为n”都没注意到结果从第一组数据就开始偏还对着调试器找了半天。后来才明白问题不在并查集而在初始状态的定义。4.4 哪些场景并查集不够用并查集只能合并不能拆分。如果需要删除边或节点就要考虑离线倒序处理把所有删除操作反过来变成加边操作如果需要输出每个集合内部具体有哪些元素就要额外维护set并配合启发式合并如果需要动态维护“两点之间最大边权最小路径”这类带边权的问题并查集需要扩展成重构树或Kruskal树。把这些边界提前搞清楚才不会在难题上盲目套模板浪费时间。很多进阶图论题都是“并查集其他数据结构”的组合知道它做不到什么比知道它能做到什么更重要。5. 拓扑排序与DAG把“先后顺序”变成一行入度表5.1 问题生活化“先后依赖”问题到处都是课程的先修关系、编译器按依赖顺序编译模块、项目任务的先后安排。这些都可以建模成有向图并且如果图里有环就说明存在互相依赖的矛盾无解。注意拓扑排序只适用于有向无环图DAG。有环的有向图不存在拓扑序这一点也是很多题目的隐藏考察点。题目经常问你“能不能完成所有课程”本质上就是在问“这张有向图有没有环”。5.2 入度视角的BFS实现拓扑排序最直观的做法是BFS版本统计每个节点的入度把入度为0的节点入队它们没有前置依赖可以先行处理然后不断弹出一个节点把它指向的每个邻居入度减1减到0就入队。弹出的顺序就是满足依赖关系的一种拓扑序。queueint q; for (int i 1; i n; i) if (indeg[i] 0) q.push(i); int cnt 0; while (!q.empty()) { int u q.front(); q.pop(); cnt; for (int v : g[u]) { if (--indeg[v] 0) q.push(v); } } // cnt ! n 说明图中存在环拓扑排序失败这个模板我建议从头默写一遍因为太常考了。比起DFS版本BFS版本的好处是入度表是显式的调试时打印入度数组一眼就能看出问题在哪。5.3 课程表题的建模过程这类题的输入通常是一堆[先修课, 后修课]的依赖对。我的建模步骤是把课程编号映射成节点对每个依赖对从先修课向后修课连一条有向边然后跑拓扑排序。如果最终弹出的课程数量等于总课程数说明没有环可以完成全部学习否则说明存在互相依赖的矛盾。难的不是算法本身而是把自然语言翻译成图的这步谁是节点、谁是边、方向是什么。我见过不少人把边方向建反结果整个拓扑序反过来却还能“正常”跑出一串序列直到检查答案时才懵。所以每次开始写代码前先花一分钟在纸上标清楚“由谁指向谁”。5.4 三类常见变体要求字典序最小的拓扑序把普通队列换成优先队列每次弹出编号最小的入度为0节点。要求判断拓扑序是否唯一在每一轮里如果队列中不止一个节点说明至少存在两种可行拓扑序。要求输出所有可行拓扑序节点数不多时用回溯枚举每层选择不同的入度为0节点。这三种变体都是对基础模板的简单改造但面试里很爱考“判断唯一性”这个点因为它需要你理解拓扑排序的过程而不只是背代码。6. 本轮实测复盘模板、细节与打卡心态6.1 手写模板和“抄一遍”的区别肉眼可见第49天结束part1时我本来打算直接冲part2后来拿张纸默写DFS/BFS模板发现自己居然会漏掉visited标记的位置。这个教训让我在part2再也不敢只背不写第一天就把Dijkstra、Kruskal、Prim、拓扑排序全部从零默写再用随机小图和暴力算法对拍验证逻辑。这个过程很花时间但收益极大之后做题时模板是肌肉记忆的一部分不用临时查资料脑子可以专注在建模上。我强烈建议每个阶段结束之后都做一次“模板默写对拍验证”别等到了赛场上才发现自己的模板是抄的。6.2 最容易出事的数据细节清单重边邻接矩阵存图时要取最小权值邻接表堆优化的Dijkstra天然会通过松弛取到最优结果所以影响不大。自环在Kruskal里可以直接跳过两端点同集合一定成环在拓扑排序里会造成入度减不完表现为节点数对不上。孤立点连通块问题里要单独统计最小生成树问题里会导致cnt永远到不了n-1也就是原图不连通。INF的取值不能设成int最大值dist[u]w会溢出成负数。我用long long的4e18级别并统一所有距离变量为long long。并查集初始化很多人merge前忘了先把parent数组初始化为自身的下标查了半小时才发现是初始化问题。这些坑单独看都很蠢但组合起来会让调试体验极其酸爽。我建议把清单贴在编辑器旁边每次提交前逐项扫一遍。6.3 关于“day 50打卡”这件事我想说点更实在的打卡最大的意义不是那串连续的天数而是它逼着你每段时间产出看得见的成果。以我的体验真正拉开差距的是“阶段复盘”而不是“每日更新”。如果某天晚上什么都没学会那打卡数字也只是自欺欺人。给同样在day N打卡的人一个建议每个阶段结束之后花一整个晚上重做阶段内的经典题。我今天就重做了part1的岛屿类题目手感明显不一样很多当时漏掉的边界条件比如一格岛屿、全是陆地、边缘触界这次都想清楚了。这种复盘的性价比远高于急着往前再冲三章。6.4 下一步的路线图图论part2显然不止这几个主题。我给自己定的路线是最短路径系列Dijkstra/SPFA/Bellman-Ford/Floyd之后把最小生成树彻底吃透再补拓扑排序的变体之后进入图的连通性强连通分量、缩点、割点割边网络流作为选学放在最后。每块都会比前面更绕但有了这几周实操打底我至少知道该怎么学先把模板写到肌肉记忆再做变形题验证理解最后回头复盘补齐漏洞。如果你现在也卡在最短路径或者最小生成树的某个坎上别急着怀疑自己。把那道题放下把算法从最原始的贪心假设开始重新推一遍很多坑会自然消失。这比我见过任何“三天学会图论”的速成攻略都靠谱。
空间约束下实现稳定性保障)
