最近把《王道论坛计算机考研机试指南》第七章“图论”完整过了一遍顺手把书页翻得全是折角和批注。这一章是整本书里我花时间最多、也最想单独写一篇笔记的章节——图论题在机试里的地位太特殊了它不像排序、字符串那样一上来就能无脑套模板也不像数学题那样纯靠推理而是典型的“代码不难写思路容易偏”的题型。如果你正在准备计算机考研的复试上机或者刚把前六章的链表、树刷完准备迈过图论这道坎这篇笔记应该能帮你少走不少弯路。先说结论第七章的核心考点非常集中翻来覆去就是图的存储、并查集、最小生成树、最短路径、拓扑排序这几板斧。但就是这几板斧几乎覆盖了各高校上机题库里三分之一以上的题型。原书的代码风格偏朴素很多模板可以直接背但我在实际刷题过程中发现有些细节光看书根本不会意识到非得到OJ上跑一遍、踩一遍坑才能真正理解。所以这篇读书笔记我想换个方式写不完全按照章节顺序复述而是按“考点地图 核心模板 代码细节 刷题复盘 踩坑实录”五个角度来拆解配合我在刷题时的真实体会。1. 第七章到底在讲什么一张图看清图论考点地图1.1 先搞清楚这章覆盖哪些高频考点第七章的目录乍一看挺唬人图的基本概念、图的存储、深度优先遍历、广度优先遍历、并查集、最小生成树、最短路径、拓扑排序洋洋洒洒好几十页。但如果把目标锁定在“机试会考什么”这个层面你会发现内容高度收敛。按我的理解整章其实就是在讲五件事把图存下来能用什么结构就用什么结构邻接矩阵、邻接表判断图里有哪些连通分量哪些点能互相到达遍历、并查集在保证连通的前提下怎么让边的总权值最小最小生成树从某个点出发到另一个点怎么让路径总权值最小最短路径有向无环图上怎么确定一个合理的前后顺序拓扑排序。书里最开始讲图的基本概念时花了很大篇幅解释顶点、边、有向图、无向图、度这些概念如果你本科数据结构课认真听过大概率是熟悉的内容。我是直接跳过的但不建议完全跳过——因为后面讲邻接矩阵和邻接表时很多代码细节都跟这些基础定义绑定在一起比如无向图的邻接矩阵为什么是对称的有向图的出度和入度分别在存储里怎么体现这些概念不牢固写代码时很容易在一个很蠢的地方卡住。1.2 为什么说图论是机试的“分水岭”我在图书馆刷真题时有一种很明显的感受前六章的题很多同学能靠“背模板 堆题量”硬啃下来但到了图论这里光背模板已经不够了。因为图论题最难的从来不是某个算法的代码本身而是“这道题到底该用哪个算法”。同一道题你用BFS求最短路径也会得到正确输出但数据范围一大就超时你用Dijkstra处理负权边样例过了但提交全是答案错误。这种“想到了什么就写了什么”的策略在前面章节还可以靠降难度混过去到了图论基本行不通。我查了一组数据印象很深某在线评测平台上收录的几百道考研机试真题里直接或间接考察图论的题目占比接近三分之一而且多数是中等难度的压轴题。这意味着什么说明机试想拿高分图论不是“会不会”的问题而是“熟练到什么程度”的问题。第七章刷一遍只是起步真正拉开差距的是你能不能做到看完题意十秒内判断出题目在考察哪个算法然后直接启动对应模板。1.3 读书前需要先补的三个基础概念原书第七章开头有一段概念铺垫我当时读得快差点跳过后来发现有两个点在刷例题时反复被用到必须提前理解透第一个是“连通分量”。无向图里如果两个顶点之间存在路径就说它们是连通的一个图里所有互相连通的点构成一个连通分量。很多机试题的题面看着很长其实核心就是“数一数这个图有几个连通分量”比如著名的畅通工程系列题目问“还需要修几条路才能让所有城市都连通”本质就是求连通分量个数减一。第二个是“环”。无向图的环会影响最小生成树的可行性判断有向图的环会影响拓扑排序的“是否存在合法序列”。书里讲最小生成树时没有专门讲环但Kruskal算法里“如果这条边的两个端点已经在同一个集合里就跳过它”这个操作本质上就是在避免成环。第三个是“稀疏图和稠密图”。这直接决定了你选邻接矩阵还是邻接表、朴素Dijkstra还是堆优化Dijkstra。我自己的判断标准很简单顶点数总和在1000以内邻接矩阵随便用顶点数过万老老实实上邻接表加堆优化。2. 图的存储别一上来就无脑邻接表2.1 邻接矩阵的实现细节与适用场景书里给的邻接矩阵代码很短核心就是开一个二维数组G[i][j]表示顶点i到顶点j的边权没有边就填一个足够大的数。我看到不少同学的笔记在这一节只记了三行觉得很没用但我在刷题时发现至少有三个细节特别容易出事。第一个是数组初始化。机试OJ的很多测试数据不会只跑一组如果你用的全局数组上一组数据的残留会影响下一组结果。书里的代码没有强调这一点但我建议每次输入前用memset或者循环重置整个数组。memset的坑在于只能赋0或者0x3f这种特殊值如果你想赋成很大的数标准做法是memset(G, 0x3f, sizeof(G))因为0x3f3f3f3f在int范围内足够大而且两个0x3f3f3f3f相加不会溢出int。这一点我在刷最短路径题时深有体会也有不少新手这里是拿个1000000当INF结果两个INF一加变成负数直接导致Dijkstra跑出错误答案。第二个是对角线初始化。无向图G[i][i]要赋值为0因为自己到自己最短路径就是0。很多人初始化矩阵时把所有位置都填了INF唯独漏了自己到自己结果Floyd一跑对角线全变成了路径长度输出就乱了。书里的代码图和例题之间其实没有特别强调这点属于那种不踩坑就永远不知道的细节。第三个是空间规模判断。顶点数n如果是1000邻接矩阵开1001x1001的int数组大概4MBOJ上完全够用如果n到了100000再开邻接矩阵就完全不现实了这时候必须换邻接表。我用一个很简单的原则顶点数平方超过1000万就不要再想邻接矩阵了。2.2 用vector模拟邻接表王道书里的实用写法邻接表这块书里的实现用的是结构体数组加vector也就是每个顶点挂一个链表但用vector替代了手写的链表指针。很多科班同学一开始会纠结“为什么不学真正的链式前向星”我自己也纠结过后来发现完全没必要。vector邻接表的代码核心就那么几行struct Edge { int to; int weight; }; vectorEdge adj[MAXN]; void addEdge(int u, int v, int w) { adj[u].push_back({v, w}); // 如果是无向图还要加 adj[v].push_back({u, w}); }书上建议的写法是直接把边信息塞进vector容器里用到哪个顶点就去哪个顶点的vector里遍历。这种做法的最大好处是代码直观、不容易写错指针在机试这种限时场景里代码的可写性往往比运行效率更重要。真的遇到那种顶点数特别大、边数也特别多的题目vector存边配合vector 的排序操作也基本够用未必非要手写链式前向星那种硬核结构。2.3 我读书时在存储这节做的旁批我的笔记在这一节写了两条对自己最有用的话。第一条是“看到题先判数据范围再选存储方式”。有些题目输入的顶点数看着很大但边很少这时候用邻接表会舒服得多反过来如果题目明显是一个边数很密集的完全图邻接表的vector反而容易因为频繁push_back而慢邻接矩阵更稳。第二条是“无向图加边记得加两条”。这句话看起来很废话但我真见过有人把addEdge只写一次导致遍历时只走了一个方向连通分量算错题目直接零分。3. 并查集与最小生成树机试里最值的“连通性组合拳”3.1 并查集模板路径压缩和按秩合并一个都不能少学习第七章时我一度以为并查集只是最小生成树的“辅助工具”后来刷题多了才发现它本身就是高频考点。题目会直接问你“能否连通”“是否属于同一集合”“图中还有多少孤立点”这些本质都是并查集。关于并查集模板书里写得很清楚核心就两个操作查找root和合并集合。我最初照着书敲了一个find函数递归写法测试数据小的时候完全没有问题后来在OJ上连续超时才想到是递归深度和路径压缩的写法不对。再看我的笔记我最后稳定使用的模板是这样int father[MAXN]; int find(int x) { return father[x] x ? x : (father[x] find(father[x])); } void unionSet(int a, int b) { int u find(a); int v find(b); if (u ! v) { father[u] v; } }这条递归加路径压缩的写法理论上在极端数据下可能会有递归栈溢出的风险实际练习中很少触发。我见过不少人喜欢把find的路径压缩写成循环版本也很好用只是我喜欢递归的简洁性看个人习惯。不过有一个点值得提醒如果题目数据量真的很大建议每次合并时用一条if判断father数组大小来“按秩合并”也就是把深度小的树并到深度大的树上。书上没细提但在那种夸张数据下这能稳定避免退化成链表。3.2 为什么Kruskal在机试里比Prim更常用最小生成树这块书里同时介绍了Prim和Kruskal两个算法。以我刷题的经验来说如果你资源有限只想记一个记Kruskal理由很简单Kruskal的代码不需要建图结构只需要把所有边拎出来按边权排序然后用并查集逐个加边代码量非常短而且天然适配“边集数组”这种最简单的存储方式。struct Node { int u, v, weight; bool operator(const Node other) const { return weight other.weight; } }; vectorNode edges; void kruskal() { sort(edges.begin(), edges.end()); int cnt 0; int total 0; for (auto e : edges) { if (find(e.u) ! find(e.v)) { unionSet(e.u, e.v); total e.weight; cnt; if (cnt n - 1) break; } } }这个模板我默写过不下十遍每次都是三分钟内能写完。书里做例题“还是畅通工程”的时候把整个流程演示得非常清楚我当时是第一遍看就能直接照着敲出提交通过这种成就感对建立信心很重要。至于Prim我的建议是理解为主不用花太多时间背模板。因为Prim在稠密图上有一定优势但机试里真正卡到必须用Prim才能过的稀疏题目很少多数题目用Kruskal在时间限制内都能完成。3.3 刷题复盘畅通工程系列怎么套模板原书第七章收录了经典的“畅通工程”系列题。我第一次做的时候兴致勃勃地想先建图、再跑一遍图遍历后来看了题解才发现这题根本不用建图只输入城市数量和道路关系然后用并查集看有几个连通分量就行。具体操作是把已有的道路两端union进同一个集合然后遍历所有城市数一数有多少个根节点根节点数量减一就是要修的公路条数。这个思路我第一次接触时觉得有点“犯规”后来才想明白这其实是机试的一个核心套路能用并查集解决的就不要上高级图算法。很多初学者容易被题面唬住觉得“图论题必须写遍历或者MST”但机试考的是快速解决问题不是炫技。所以我把这题的标准解法写进了笔记旁边标注了六个字“先想最简单模型”。4. 最短路径Dijkstra与Floyd的选择难题4.1 单源最短路径Dijkstra朴素版到优先队列版最短路径是第七章里最硬核的内容因为它的代码比前面所有算法都长而且边界条件特别多。书里重点提的是Dijkstra算法我当时照着书写了一遍朴素版的模板后来又自己优化成了优先队列版。朴素版的思路很容易理解每次从未访问的点里挑一个离起点最近的点用它去松弛它的邻居。写起来是一次双重循环复杂度O(n^2)。具体代码我放在下面很多细节都是书里没有特意强调的#include bits/stdc.h using namespace std; const int INF 0x3f3f3f3f; int G[1010][1010]; int dis[1010]; bool vis[1010]; void dijkstra(int s, int n) { fill(dis, dis n 1, INF); memset(vis, 0, sizeof(vis)); dis[s] 0; for (int i 1; i n; i) { int u -1; int minDist INF; for (int j 1; j n; j) { if (!vis[j] dis[j] minDist) { minDist dis[j]; u j; } } if (u -1) break; vis[u] true; for (int v 1; v n; v) { if (!vis[v] G[u][v] ! INF dis[u] G[u][v] dis[v]) { dis[v] dis[u] G[u][v]; } } } }这里有一个我后来才懂的关键点为什么初始化时要fill而不是memset因为INF是0x3f3f3f3fmemset是按字节赋值的fill则可以直接把int数组每个元素赋成同一个值。如果你用了memset(dis, 0x3f, sizeof(dis))虽然也能得到一个很大的初值但读者容易混淆。书里可能没在这个细节上纠结但你自己写的时候必须清楚自己用的是哪种赋值方式。优先队列版的Dijkstra是用priority_queue维护“当前离起点最近的点”每次从堆顶取出一个点如果它已经被访问过就跳过否则更新它邻居的dis值。这个版本的复杂度是O((nm)logn)在稀疏图上有显著优势。我自己的经验是n超过2000就别再用朴素版了直接把优先队列版背下来。4.2 Floyd算法三重循环千万别把k放错位置Floyd在整个第七章里占的篇幅不算特别大但各高校机试却非常喜欢出这种“多源最短路径”题。它的代码核心就是三重循环for (int k 1; k n; k) { for (int i 1; i n; i) { for (int j 1; j n; j) { if (G[i][k] G[k][j] G[i][j]) { G[i][j] G[i][k] G[k][j]; } } } }中间层用k作为中转点这个顺序千万不能写反。如果写成先循环i再循环k你会在不知不觉中加入一些“斜着走”的不合理路径得到错误结果。记住这句话k是最外层的循环它代表“允许使用前k个点作为中转点”。初学者如果懂了这一层含义就永远不会把循环顺序写错。Floyd的好处是代码短、思路无脑缺点是复杂度O(n^3)适合n在200到300以下的情况。我刷真题时见到过一道“多个城市之间两两最短路”的题n只有50明显就是为了让你用Floyd的。如果你审题时发现题目要求任意两个顶点之间的最短路径而且顶点数很小那就别考虑Dijkstra跑n遍了直接Floyd一把梭。4.3 边界条件与负权边问题看书时容易忽略的一个重点书上在讲最短路径时提到Dijkstra不能处理负权边但没有特别展开说“为什么”。我当时读到这里其实有一点困惑负权边不是只要我把判断条件写着dis[v] dis[u] w自然也能更新吗后来想通了一件事Dijkstra的核心假设是“已经确定最短路径的点后续不会再被更新”但如果存在负权边有可能一条路径先变长再通过负权边变短这个点被标记访问后就不会再被松弛了答案就错了。所以我在笔记里画了一个大括号旁边写着“题目没说明边权为正时默认Dijkstra不能用问清楚再动手。”如果遇到负权边标准做法是Bellman-Ford算法或者SPFA这两个算法在机试里的出现频率比想象中高尤其SPFA很多人因为Dijkstra刷多了遇到带负权的小数据题会直接条件反射地写出Dijkstra结果错得莫名其妙。建议把SPFA的判负环写法也扫一眼不一定要死记但至少看到题目提“负权”时知道它属于哪一类。5. 拓扑排序有向无环图的基础题型5.1 入度为0的队列思路拓扑排序这一节书里的定义讲得很严谨但我自己的理解方式更直白一些拓扑排序就是一种“先后顺序”。比如修课程必须先修完某门再学另一门把这些课程的依赖关系建成有向边最后输出的顺序就是拓扑序。放在图的存储里我们维护一个入度数组入度代表“还有几门课挡在我前面”。算法流程也很简单每次找一个入度为0的顶点输出然后把它指向的所有顶点入度减1重复这个过程。代码实现时我用的是一个普通队列把所有入度为0的顶点初始入队然后依次出队处理。void topoSort() { queueint q; for (int i 1; i n; i) { if (inDegree[i] 0) q.push(i); } int cnt 0; while (!q.empty()) { int u q.front(); q.pop(); cnt; for (auto [v, w] : adj[u]) { inDegree[v]--; if (inDegree[v] 0) q.push(v); } } if (cnt ! n) { // 说明有环 } }这段代码里有两点值得标记一是拓扑排序不要求你输出图里所有顶点的唯一顺序只要满足约束就行所以可能出现多个合法答案二是最终如果出队数量不等于n说明图中存在环不存在合法的拓扑序。这一点在机试里非常常见因为很多判断DAG有向无环图的题目本质就是在问“拓扑排序能不能跑完全部顶点”。5.2 拓扑排序的题目变形不只是“给一个顺序”拓扑排序在实际题目里是不太会直接挂“拓扑排序”三个字的。比如某道题说一个工程有若干步骤每个步骤有前置依赖问能否按顺序完成或者问“最少需要多少时间完成”可能就是在这层壳子下的拓扑排序。我印象最深的变种是“判断图中是否有环”的题。你无需真的输出拓扑序只需要在跑完一遍之后检查cnt是否等于n就行了。另一个变种是字典序最小的拓扑序做法是把队列换成优先队列每次取当前编号最小的入度为0点输出顺序自然就是字典序最小的。这个技巧书里没有专门讲但我刷真题时真遇到过建议大家顺手记一下代码改动只有一行收益却很高。6. 边读边刷我的第七章刷题顺序与复盘6.1 高效刷题顺序建议很多人读这一章时会踩一个坑从第一页开始逐行读读完才想“我要不要去做题”结果读到最短路径时前头并查集已经忘了一半。我自己的刷法是把第七章切成三段读每读完一小段算法介绍就立刻去OJ找几道对应模板题来写第一段图的存储 图的遍历刷2到3道连通分量题第二段并查集 最小生成树刷3到4道畅通工程类题第三段最短路径 拓扑排序刷3到4道最短路径和DAG题。这种“三段式”节奏的好处是每个算法的模板都能在当天得到强化你可以趁热把代码默写一遍。我的笔记里就清晰地记着第一遍我把Kruskal模板默写了六遍才达到“手不停笔”的状态但第二遍开始写最短路径时已经能一口气写完一整个Dijkstra说明那个阶段的基础已经比较牢了。6.2 怎么对待“代码能过样例但提交错误”的题目我在这章刷题时有一个很深刻的体验很多时候你在自己电脑上运行样例全对一提交就是错。查了半天最后发现既不是算法选错也不是代码语法错误而是初始化问题。举个例子有一道单源最短路径的题样例输出一直正确但我低估了多组输入的情况dijkstra函数里我忘了先把优先队列或者dis数组重置结果上一组测试数据的dis值残留到了下一组。这种错误最恶心的地方在于它不稳定很容易在你觉得“稳了”的时候突然给你一个WA。所以我的笔记里专门用红笔写了一行“所有数组每跑一次输入用例都必须重新初始化。”另外书里很多例题用的变量名是n、m、u、v如果你刷题时也这么用务必注意全局变量与函数局部变量的作用域冲突。我见过有同学把全局n在main里重新定义了一个局部变量结果图里循环范围全错调试了快一个小时才发现是变量名被遮蔽。6.3 表格复盘哪些题我刷完瞬间明白哪些题让我怀疑人生我梳理了一份自己的错题复盘表在这里也分享给大家参考因为每个人的弱项不一样但整体分布是有规律的题目类型我的主要错误改正后的心得无向图求连通分量漏掉重复加边无向图addEdge必须两条否则图不完整最小生成树Kruskal忘记对边排序Kruskal的灵魂就是边权排序不能省单源最短路径DijkstraINF太大导致溢出用0x3f3f3f3f两个相加减一算就是大约正数范围的一半拓扑排序判断环没数输出顶点数cnt与n不等一定是有环了Floyd的循环顺序k放在内层记忆“中转点必须先枚举”这张表的价值在于它帮我建立了“看到WA后第一反应查什么”的思维顺序。后来我再遇到图论题几乎都会下意识先检查三个地方数组大小、初始化、循环顺序。7. 我踩过的几个坑和最后一页笔记7.1 四个值得单列的坑位这一章刷下来我把踩过的坑分了四类也是我读书时在页边反复写的“警示牌”。一个是递归find函数虽然能压路径但如果你在考试时开了超大数据递归栈深度可能爆掉。遇到这种极端情况建议改成循环写法int find(int x) { int root x; while (root ! father[root]) root father[root]; while (x ! root) { int next father[x]; father[x] root; x next; } return root; }第二个坑是邻接表遍历时忘了判断边是否存在。我在写Dijkstra时用邻接矩阵就习惯了看G[u][v] ! INF但换到邻接表后只需要访问adj[u]里的每条边根本没有“这条边不存在”的概念不用加额外判断。可是在最短路径松弛时我却习惯性地又写了一个if加了也无妨但没写也不影响。第三个坑是有向图的度。拓扑排序要统计入度无向图不用管入度出度所以代码模板也要分开。我在同一个cpp文件里同时写过无向图和有向图结果忘记对数组做拆分程序跑出来一团糟。现在我的习惯是凡是涉及入度的变量名全部带前缀比如inDeg不带前缀的一律当无向图处理。第四个坑是输出格式。图论题经常出现“无穷大”的情况题目如果要求输出-1你就不能直接打印INF那个巨数。我刷题时老忘记这个转换交了好几次才发现题目明明写了如果不可达就输出-1。所以我在笔记里补了一条“读题时把输出要求圈出来不要在代码里默认输出INF。”7.2 我读书时写在最后一页的话每次刷完一章我都有个习惯在那一章的最后一页写几句只给未来的自己看的备注。第七章我写的是“图论题不是看你背了多少模板而是看你看到题目时能不能在一分钟内完成问题转换这个题问的是连通性、最小总代价、最短路径还是顺序合法性。转换对了剩下的就是代码肌肉记忆。”这句话陪我刷完了之后的好几套真题每次遇到卡壳的题我都会先退一步把题面浓缩成一个“目标描述”再决定调用哪一段模板。事实证明这种方式比上来就套算法要可靠得多。最后再分享一个小经验图论这章的内容读一遍和手写一遍完全是两回事。我当时读完以为自己懂了Kruskal和Dijkstra结果默写模板时总在find的路径压缩、Dijkstra的初始化上卡壳。所以如果你时间有限我强烈建议把所有模板都放到编译环境里亲手敲一遍敲到自己形成肌肉记忆为止。机试考场上的紧张氛围里真正能救你的不是“我记得思路”而是“我的手自己会写”。
