打算法竞赛的同学应该都有体会图论相关的模板总是占代码量的大头。平时刷题倒还好一到正式比赛短暂的时间内既要读题、想解法、调试还得从零手撸一遍最短路、最小生成树那种紧张感我到现在都记得。后来我把自己常用的图论模板整理成了固定的一套每次直接抄比赛时省下来的时间全用来分析和验证思路效果特别好。这篇文章就把我平时高频使用的图论算法模板做个汇总附上一些容易踩坑的细节适合正在学图论、备战ACM或NOIP的读者参考。我整理的这些模板都用C写遵循几个原则能用数组就不用复杂容器、能静态就坚决不动态分配、所有代码都压到尽量短且不容易写错的结构。这么做不是炫技而是比赛环境下代码越短、越贴近自己熟悉的格式越不容易在紧张时写出隐蔽bug。下面我按照最短路、最小生成树、拓扑排序、二分图这几个常见模块来拆解。1. 模板的整体设计思路与准备工作1.1 为什么比赛选手需要固定模板先说一个很多人忽略的事实图论题真正难的不是背模板而是把问题抽象成图。但抽象完了如果基础代码都写不顺思路再漂亮也白搭。比如最短路里的Dijkstra堆优化写法如果不熟练现场调试队列优先级、dist数组更新顺序随随便便就花掉二十分钟。而一套固定的、自己亲手验证过的模板可以把写代码的时间压缩到两三分钟把精力留给真正的思考。我自己早期也犯过这个毛病每次写模板都重开一份觉得反正会写直接上手就行。后来发现写出来的代码风格不一致一会儿用vector邻接表一会儿用链式前向星出错了自己都看不清。整理模板之后不仅写题快了出错率也明显下降因为每个模板都反复使用过边界条件和陷阱都烂熟于心。1.2 模板的通用存储方式链式前向星还是vector邻接表这是我在实战中最纠结过的选择。vector存邻接表写起来很直观遍历也方便但比赛偶尔会遇到卡时间的题vector的push_back会有一定开销而且封装成结构体后内存不连续对缓存不友好。链式前向星写起来稍微绕一点用数组模拟链表但效率高、空间紧凑而且支持多重边所以在竞赛环境里我更推荐链式前向星。struct Edge { int to, w, nxt; } e[MAXM]; int head[MAXN], tot; void init() { memset(head, -1, sizeof(head)); tot 0; } void addEdge(int u, int v, int w) { e[tot].to v; e[tot].w w; e[tot].nxt head[u]; head[u] tot; }这里head数组初始化为-1遍历时用for(int i head[u]; i ! -1; i e[i].nxt)非常好用。需要注意的是addEdge是无向图的时候要调用两次把u-v和v-u都加进去。有重边的情况下这种写法天然支持因为新增的边会插到链表头部不会覆盖已有边。1.3 模板的注释与变量命名习惯我整理模板的原则是变量名尽量短但可读比如u、v表示端点w表示边权dist、vis这种一眼就能看懂。注释这块我的建议是模板里只写关键提示比如“这里为什么要判vis”而不是把每一行都注释一遍。注释写多了比赛时反而干扰阅读。还有一点很重要所有数组大小都预留了MAXN和MAXM的宏定义每次使用前按题目要求改这两个值就行。我习惯把上限设为题目上限加10防止边界访问越界。这个习惯帮我避免了不少RERuntime Error你想一下如果n刚好等于数组长度访问n1的位置就炸了所以多开几个位置是性价比极高的防御。2. 最短路算法模板Dijkstra、SPFA与Floyd2.1 堆优化的Dijkstra单源非负权最短路Dijkstra是图论里出镜率最高的算法核心思想是贪心每次从未确定的点中选出距离最小的点用它去松弛连边。当边权非负时这个贪心是正确的。朴素写法每次找最小距离需要O(n)堆优化后用优先队列把这一步降到O(logn)整体复杂度O((nm)logn)适用于大多数字典序或者路径统计类题目。typedef pairint, int PII; // {distance, vertex} const int INF 0x3f3f3f3f; void dijkstra(int s) { priority_queuePII, vectorPII, greaterPII pq; for (int i 1; i n; i) dist[i] INF; dist[s] 0; pq.push({0, s}); while (!pq.empty()) { PII p pq.top(); pq.pop(); int d p.first, u p.second; if (d ! dist[u]) continue; // 过期标记 for (int i head[u]; i ! -1; i e[i].nxt) { int v e[i].to, w e[i].w; if (dist[v] dist[u] w) { dist[v] dist[u] w; pq.push({dist[v], v}); } } } }这里有个细节pair排序时先按距离再按点编号所以在优先队列里用greaterPII就能得到小顶堆。还有一个很多新手不理解的地方为什么不用vis数组标记已确定的点。因为优先队列里可能出现同一个点被多次push的情况第一次出队的才是最小距离后面出队的距离一定更大用if(d ! dist[u]) continue;直接跳过即可效果等价于vis但代码更简洁。注意这里INF用0x3f3f3f3f而不是INT_MAX是因为后面如果做dist[u] wINT_MAX正数会溢出变成负数直接导致算法出错。0x3f3f3f3f足够大两个相加也不会溢出int范围。2.2 SPFA与负权图的处理SPFA本质是Bellman-Ford的队列优化适合判断负环或者边权存在负数的情况。它的思想是只有被松弛过的点才可能引起其他点的松弛所以用一个队列维护被更新过的点反复入队出队。虽然SPFA在随机图上的表现不错但出题人会构造网格图或者菊花图卡它最坏复杂度还是O(nm)所以遇到不存在负权的题老老实实用Dijkstra。bool inq[MAXN]; int cnt[MAXN]; // 记录入队次数用于判断负环 bool spfa(int s) { queueint q; memset(dist, 0x3f, sizeof(dist)); memset(inq, false, sizeof(inq)); memset(cnt, 0, sizeof(cnt)); dist[s] 0; q.push(s); inq[s] true; while (!q.empty()) { int u q.front(); q.pop(); inq[u] false; for (int i head[u]; i ! -1; i e[i].nxt) { int v e[i].to, w e[i].w; if (dist[v] dist[u] w) { dist[v] dist[u] w; if (!inq[v]) { q.push(v); inq[v] true; if (cnt[v] n) return false; // 存在负环 } } } } return true; }判断负环的原理是从任意点出发到某个点的最短路最多经过n-1条边如果一个点的入队次数大于n说明存在一条被反复松弛的负权回路。这个模板我在做差分约束系统题目的时候也经常用因为它能检测出不满足约束条件的环。注意如果题目明确没有负环也可以去掉cnt数组这部分只保留松弛逻辑代码会更短。2.3 Floyd多源最短路与动态规划视角Floyd的代码极短三层循环就完了但它背后的动态规划思想容易被忽略。dp[k][i][j]表示从i到j、中间只经过编号小于等于k的点时最短路的长度。最终答案就是dp[n][i][j]。滚动掉第一维后就变成了标准的二维Floyd写法。for (int k 1; k n; k) for (int i 1; i n; i) for (int j 1; j n; j) if (mp[i][j] mp[i][k] mp[k][j]) mp[i][j] mp[i][k] mp[k][j];这里的初始化要注意mp[i][i]0其他点对如果有边就设为边权没有边就设为INF。为什么k要在最外层因为mp[i][j]在更新时用到的mp[i][k]和mp[k][j]必须是只经过前k-1个中间点的结果如果k放在内层会提前使用包含k这条路径的信息导致重复经过k点结果就不对了。Floyd适合n不超过500的场景复杂度O(n^3)超过这个规模就得考虑Johnson算法或者跑n次Dijkstra了。3. 并查集与最小生成树模板3.1 带路径压缩和按秩合并的并查集并查集其实不算严格的图论算法但它在判断连通性、找环、合并集合上太常用了几乎每道图论题都能用上。路径压缩把树的高度压到接近O(1)按秩合并能保证树的高度始终保持在对数级别两者结合后单次操作的均摊复杂度接近常数。int fa[MAXN], rnk[MAXN]; void init(int n) { for (int i 1; i n; i) fa[i] i; memset(rnk, 0, sizeof(rnk)); } int find(int x) { return fa[x] x ? x : fa[x] find(fa[x]); } void unite(int x, int y) { x find(x); y find(y); if (x y) return; if (rnk[x] rnk[y]) swap(x, y); fa[y] x; if (rnk[x] rnk[y]) rnk[x]; }这里有个小坑find递归在链很长时虽然路径压缩后会变短但极端情况下第一次递归可能深度很大导致栈溢出。通常题目给的数据范围不会那么极限但如果你用这套模板跑百万级别的数据建议改成非递归版本或者把rnk换成fa数组的负值表示集合大小。非递归find有一种写法很简单先用循环找到根再把路径上所有点平铺到根上性能非常稳定。经验我在处理“判断一棵树是否形成环”这种问题时会边读边做unite。每次连边时若两个端点已经在同一集合里说明这条边会形成环记录下来即可。这个技巧在Kruskal算法里也是核心判断逻辑。3.2 Kruskal最小生成树与贪心证明Kruskal的思路特别简单把所有边按权值从小到大排序依次尝试加入生成树如果这条边的两个端点不在同一个连通块里就加入否则跳过。这个贪心正确性可以用反证法证明我们在这里不展开但实践中记住结论就够用。struct Line { int u, v, w; } edge[MAXM]; bool cmp(Line a, Line b) { return a.w b.w; } int kruskal(int n, int m) { int ans 0, cnt 0; sort(edge, edge m, cmp); for (int i 1; i n; i) fa[i] i; for (int i 0; i m; i) { int u edge[i].u, v edge[i].v, w edge[i].w; u find(u); v find(v); if (u ! v) { fa[u] v; ans w; cnt; if (cnt n - 1) break; } } return cnt n - 1 ? ans : -1; // -1表示图不连通 }这个模板里最值钱的变量是cnt它统计已经加入的边数。最小生成树在n个点的图上一定恰好有n-1条边如果跑完所有边还没凑够说明图本身不连通。用这个返回值判断一下很多题目会问“能否构成生成树”这样一次Kruskal就同时求了最小权和连通性。3.3 Prim算法与稠密图的场景适配Prim的思路和Dijkstra极像也是贪心地向外扩展区别在于Prim维护的是“当前点到已选集合的最短距离”而不是到起点的最短距离。朴素Prim适合稠密图复杂度O(n^2)堆优化版O((nm)logn)反而在稠密图上不如朴素版因为堆操作常数太大。如果题目给的m接近n^2就直接写朴素Prim。int prim(int s) { memset(dist, 0x3f, sizeof(dist)); memset(vis, 0, sizeof(vis)); dist[s] 0; int ans 0; for (int i 1; i n; i) { int u -1, minDist INF; for (int j 1; j n; j) { if (!vis[j] (u -1 || dist[j] minDist)) { u j; minDist dist[j]; } } if (u -1) return -1; vis[u] true; ans dist[u]; for (int j 1; j n; j) { if (!vis[j] mp[u][j] dist[j]) { dist[j] mp[u][j]; } } } return ans; }Prim里的mp[u][j]是邻接矩阵所以它天然适合稠密图。注意这里ans dist[u]而不是minDist累加实际上两者是一样的但我习惯用dist[u]因为遍历之后dist[u]已经被更新成最小值了。还有一个细节点我用的vis是bool数组标记点是否已经在生成树集合里这个和Dijkstra的vis含义不同别搞混。4. 拓扑排序与有向无环图的应用4.1 Kahn算法的BFS实现拓扑排序解决的是“有没有一个合法的线性顺序使得所有有向边都从前往后指”的问题。典型应用是课程依赖、编译依赖、项目排期。Kahn算法维护一个入度为0的队列不断取出队首顶点、删除它的出边、更新后续顶点的入度直到队列为空。int indeg[MAXN]; vectorint topo; bool topoSort(int n) { queueint q; for (int i 1; i n; i) { if (indeg[i] 0) q.push(i); } while (!q.empty()) { int u q.front(); q.pop(); topo.push_back(u); for (int i head[u]; i ! -1; i e[i].nxt) { int v e[i].to; if (--indeg[v] 0) q.push(v); } } return (int)topo.size() n; }最后这个topo.size() n非常关键。如果图里有环环上的节点入度永远不为0拓扑序列长度就会小于n用这个来判断图是否为DAG有向无环图很直接。最后如果要输出拓扑序直接遍历topo就行。如果题目要求字典序最小的拓扑序把queue换成priority_queue小于号改成大于号即小顶堆就行代码只改一个地方。4.2 拓扑排序与最短最长路结合有时候图里有多个入度为0的起点要求某个终点完成的最早时间或最晚时间这就是拓扑排序加DP的经典套题。处理方式是在拓扑排序的同时维护一个f[i]数组表示到达点i的最大值或最小值每松弛一条边就更新一次。因为拓扑序天然保证了所有前驱点都在当前点之前处理完所以传递性很好写。// 求最早完成时间边权表示依赖耗时 f[v] max(f[v], f[u] w); // 求最长路DAG上的动态规划 // 求最短路的场景则把max改成min但注意不能有负边和环这种写法比跑一遍SPFA或者Dijkstra快得多因为没有环只需要O(nm)线性时间。我遇到好几个“任务调度”类型的题都用这个套路比如POJ上的__Genealogical tree__和“关键路径”问题。关键路径本质就是DAG上从源点到汇点的最长路用拓扑序DP就能解。如果你对这类题不熟可以找几道带权DAG的题练一练很快就上手。5. 二分图判定与匈牙利匹配模板5.1 染色法判定二分图二分图是指能把所有顶点分成两个集合每条边的两个端点分别在两个集合里。一个图是二分图当且仅当它不包含奇环长度为奇数的环。染色法从任意未染色的点出发标记为颜色1把邻居标记为颜色2再递归处理邻居的邻居如果发现相邻点颜色相同就说明存在矛盾。bool dfs(int u, int color) { col[u] color; for (int i head[u]; i ! -1; i e[i].nxt) { int v e[i].to; if (col[v] color) return false; if (col[v] 0 !dfs(v, -color)) return false; } return true; } bool solve(int n) { memset(col, 0, sizeof(col)); for (int i 1; i n; i) { if (col[i] 0 !dfs(i, 1)) return false; } return true; }注意这里用-color来切换颜色代码特别干净。主函数里循环所有点是因为图可能不连通每个连通块单独染色。这个模板在“关押罪犯”这类题里作为判定函数非常好用配合二分答案可以解决带限制的图着色问题。5.2 匈牙利算法求最大匹配匈牙利算法解决的是“最多能凑出多少对互不冲突的配对”问题。核心思路是寻找增广路如果当前这个左点v没有匹配或者它匹配的右点能让出来位置就更新匹配关系。这个道理听起来抽象但代码里就一个递归函数。int match[MAXN]; // 右点匹配的左点编号 bool used[MAXN]; // 右点是否在当前尝试占用的路径中 bool findPath(int u) { for (int i head[u]; i ! -1; i e[i].nxt) { int v e[i].to; if (used[v]) continue; used[v] true; if (match[v] 0 || findPath(match[v])) { match[v] u; return true; } } return false; } int hungary(int n) { int res 0; memset(match, 0, sizeof(match)); for (int i 1; i n; i) { memset(used, false, sizeof(used)); if (findPath(i)) res; } return res; }这里有一个关键点必须说清楚used数组不是表示“这个右点已经被匹配过了”而是表示“在当前这一轮的findPath尝试中这个右点已经被占用”。如果不重置或者理解错了就会导致递归死循环或者跳过某些可能的路径。我刚开始学匈牙利算法的时候就在这里栽过跟头总是把used和match搞混。匈牙利算法复杂度O(n*m)n是点数m是边数。虽然理论上看起来不小但实际表现非常快因为很多时候提前返回了。如果要给二分图匹配问题做优化可以有时间再了解HK算法Hopcroft-Karp比赛里用匈牙利一般够用。6. 常见问题与排查技巧实录6.1 多组测试数据时忘记初始化这是我能想到的最常见的图论模板翻车现场。很多题目有T组测试数据如果你只写一个全局初始化函数但忘了在循环内调用那么上一组数据留下的vis、dist、head数组就会污染下一组结果。我自己的经验是写一个init(n)函数把head设为-1、tot置0、并查集重置等全部做掉并且在读入每组数据的最开始调用它。6.2 DFS爆栈的替代方案有些图论题需要用DFS比如染色法、匈牙利算法但数据规模一大递归深度可能达到10的5次方以上系统栈就爆了。解决办法有两个第一个是用#pragma comment(linker, /STACK:1024000000,1024000000)Windows环境下或者参考系统设定加大栈空间第二个是改写成非递归版本。说实话在正式比赛中选手通常无法控制编译器参数所以写递归模板时要意识到这个风险必要时改成栈模拟。6.3 数组下标从0还是从1图论的题有两种编号习惯有的从0开始有的从1开始。这本身不是问题问题是模板默认从1开始但读入数据是从0开始的忘了转换就会导致访问到错误节点。我在模板的注释里专门写了“从1开始编号如果是0-based请在所有读入的位置1”。这种因为编号习惯不同而导致的bug特别难查因为逻辑完全正确就是差了一个偏移。6.4 邻接矩阵的初始化与INF选择使用Floyd或Prim时邻接矩阵需要初始化为INF但选INF时要注意两点不能太大相加会溢出不能太小比标准最短路还短。我常用0x3f3f3f3f因为它的十进制是1061109567不到int上限的一半两个相加大约是2.1e9刚好还在int范围内。如果题目给的边权最大是10^9那INF就改成0x1f1f1f1f之类的值确保两倍INF仍然不溢出。6.5 重边和自环的处理链式前向星天然容忍重边因为所有边都存下来了Dijkstra会自行判断最小的那一条作为有效路径。但Prim用邻接矩阵时重边需要取最小值自环则直接忽略因为mp[i][i]0本身就代表不选择自环。读入的时候可以做个判断如果是重边就保持最小边权否则后读入的大边会覆盖小边导致错误。7. 模板库的构建思路与维护建议7.1 按照模块分类整理我会把模板库分成这几个文件graph_basic.cpp链式前向星、并查集、shortest_path.cppDijkstra、SPFA、Floyd、mst.cppKruskal、Prim、dag.cpp拓扑排序、关键路径、bipartite.cpp染色法、匈牙利算法。每个文件开头写一段注释标出适用场景和数据范围限制。这样比赛时可以快速定位要抄哪一段。7.2 定期用自己的模板重刷题光收藏模板没有用自己写熟了才叫自己的。我建议每周选两到三个图论经典题用模板库里的代码跑一遍顺便检查有没有可以优化的细节。比如我发现堆优化的Dijkstra在某些时候用dist d w这种判断比dist - w d更安全因为后者可能在溢出时出问题这个心得就是刷题刷出来的。7.3 模板与题解分离的个人习惯最后分享一个我自己的习惯把模板本身和用模板解的题的题解分开存放。模板库里只放“干净的”、不掺杂业务逻辑的核心算法代码题解放带题目背景、完整判断逻辑的代码。这样每次用模板时都要自己思考怎么把题目映射到算法上而不是机械地复制粘贴思维能力不会退化。图论模板这东西看起来是背代码实际上背的是边界条件、复杂度分析、适用场景的快速映射。把这些整理成自己的东西才能在真正的比赛或者面试里游刃有余。