1. 项目概述一份来自赛场的图论实战指南如果你正在备战蓝桥杯这类算法竞赛或者想系统性地提升自己的图论解题能力那么这份“个人模板”的分享或许正是你需要的。这不是一份教科书式的理论罗列而是我从第十二届蓝桥杯国赛的备赛和实战中将高频、核心的图论算法进行提炼、优化和封装后形成的“武器库”。图论问题在算法竞赛中占据着举足轻重的地位从最短路、最小生成树到拓扑排序、连通分量几乎每场比赛都会涉及。但比赛时时间紧迫现场推导并调试一个复杂算法的完整代码是不现实的。因此拥有一套经过自己反复验证、边界清晰、接口明确的模板代码是稳定发挥的关键。这份“图论篇”模板核心价值在于“实战化”和“个人化”。它不仅仅是将算法用代码实现更重要的是融入了我在刷题和比赛中积累的踩坑经验、性能优化技巧和不同场景下的适用性判断。例如Dijkstra算法何时用堆优化邻接表和邻接矩阵在什么数据规模下切换Tarjan算法求强连通分量时栈和标记数组的细节如何处理这些在标准教材中可能一笔带过但在实际编码和调试中却至关重要的问题都会在这份模板的注释和配套说明中得到解答。接下来我将逐一拆解这份模板的核心模块分享其设计思路、实现细节以及那些只有真正写过、调过、错过才能领悟的“心法”。2. 模板整体架构与设计哲学2.1 为什么需要“个人模板”很多初学者会直接从开源平台复制他人的模板这固然是快速入门的方法但存在隐患。首先你不理解其中每一个变量、每一步操作的深意调试时一旦出错将无从下手。其次别人的模板风格和习惯可能与你不同在紧张的比赛环境中使用不熟悉的代码容易增加心智负担。因此我的建议是以经典实现为蓝本在大量练习中根据自身的编码习惯和常见错误进行改造和固化最终形成肌肉记忆。我的模板设计遵循几个原则一致性所有图论算法的存储结构如邻接表保持统一减少切换成本。鲁棒性对输入数据的边界情况如负权边、自环、重边有明确的处理逻辑或注释提示。可读性关键步骤有简洁注释变量命名清晰如dist[]表示距离vis[]表示访问标记。模块化每个算法是独立的函数或类但共享基础的数据结构方便组合使用。2.2 核心数据结构选型邻接表的绝对优势在竞赛中除非题目明确给出稠密图边数接近顶点数的平方否则邻接表是唯一的选择。它节省空间遍历效率高。我的模板统一使用vector实现的邻接表对于带权图使用结构体或pair存储边。// 方式一使用vectorpairint, int first是邻接点second是边权 vectorvectorpairint, int adj(n); // 方式二定义Edge结构体可存储更多信息如边编号 struct Edge { int to, w; }; vectorvectorEdge adj(n);提示我倾向于使用方式一因为pair默认支持比较操作在放入优先队列时无需重载运算符更为简洁。仅在需要记录额外信息时才使用结构体。对于需要快速判断两点间是否有边或者需要处理边删除的特殊题目才会考虑邻接矩阵或链式前向星。链式前向星虽然空间更省但可读性稍差调试不便因此我的主模板仍以vector邻接表为主但会准备一个链式前向星的版本作为备选。3. 最短路算法模板精讲最短路是图论最核心的问题之一。模板必须覆盖三种主要场景非负权图单源最短路Dijkstra、带负权图单源最短路SPFA/Bellman-Ford、多源最短路Floyd。3.1 Dijkstra算法堆优化版竞赛中的绝对主力这是你必须熟练掌握且要写得又快又准的算法。核心是使用优先队列小顶堆不断取出当前距离起点最近的点进行松弛。// 假设图使用 vectorvectorpairint, int adj 存储 const int INF 0x3f3f3f3f; // 一个很大的数常用且两倍不会溢出int vectorint dijkstra(int start, int n) { vectorint dist(n, INF); vectorbool vis(n, false); // 可有可无用于判断是否已确定最短距离 dist[start] 0; // 优先队列pair当前距离 节点编号 priority_queuepairint, int, vectorpairint, int, greaterpairint, int pq; pq.emplace(0, start); while (!pq.empty()) { auto [d, u] pq.top(); pq.pop(); // 关键优化如果弹出的距离大于当前记录的距离说明是旧队列中的无效项直接跳过 if (d dist[u]) continue; // 如果使用了vis数组可以在这里标记vis[u]true for (auto [v, w] : adj[u]) { if (dist[v] dist[u] w) { dist[v] dist[u] w; pq.emplace(dist[v], v); } } } return dist; }实操心得与避坑指南INF的选择0x3f3f3f3f是一个魔法数字其值约为1e9且满足INF INF不会溢出32位有符号整数用memset(dist, 0x3f, sizeof dist)可以快速初始化为该值。vis数组的必要性在标准的Dijkstra教学中常用vis标记已确定最短路的点。但在堆优化版本中if (d dist[u]) continue;这行代码已经起到了同样的作用且更高效。因此vis数组可以省略简化代码。优先队列的冗余项这是最重要的优化点。当某个点u的距离被更新多次时队列中会存在多个{dist1, u},{dist2, u}... 的项。我们只处理第一个即距离最小的弹出的项后续弹出的更大距离的项通过if (d dist[u]) continue;直接跳过。这能避免大量无效操作。边权为非负这是Dijkstra算法的前提。如果图中存在负权边算法可能得出错误结果。此时必须使用SPFA或Bellman-Ford。3.2 SPFA算法虽有名声但需慎用SPFA (Shortest Path Faster Algorithm) 是Bellman-Ford的队列优化版本在随机图上效率很高但最坏时间复杂度仍为O(VE)可能被特殊数据卡超时。因此在竞赛中如果题目没有负权边一律使用Dijkstra。只有明确存在负权边或负权环时才考虑SPFA。// SPFA 判断从start点出发是否存在负权环通过记录入队次数 bool spfa(int start, int n, vectorint dist) { vectorint cnt(n, 0); // 记录入队次数 vectorbool inQueue(n, false); queueint q; dist.assign(n, INF); dist[start] 0; q.push(start); inQueue[start] true; cnt[start]; while (!q.empty()) { int u q.front(); q.pop(); inQueue[u] false; for (auto [v, w] : adj[u]) { if (dist[v] dist[u] w) { dist[v] dist[u] w; if (!inQueue[v]) { q.push(v); inQueue[v] true; cnt[v]; // 如果入队次数超过n次说明存在负权环 if (cnt[v] n) return true; } } } } return false; // 不存在从start可达的负权环 }注意事项判断负权环上述代码通过记录每个点的入队次数是否超过n来判断是否存在从起点start可达的负权环。这是SPFA的一个重要应用。性能风险在非负权图上SPFA的效率不稳定。有些出题人会特意构造网格图等数据来使SPFA退化。因此“遇事不决用Dijkstra”是更稳妥的竞赛策略。3.3 Floyd算法多源最短路的简洁之选Floyd算法基于动态规划代码极其简洁适用于顶点数不多通常n500的多源最短路问题或者需要计算任意两点间距离的场景。// 初始化dist[i][i] 0, 有边则为边权无边则为INF vectorvectorint dist(n, vectorint(n, INF)); for (int i 0; i n; i) dist[i][i] 0; // ... 读入边初始化dist[u][v] w for (int k 0; k n; k) { for (int i 0; i n; i) { // 一个小优化如果dist[i][k]已经是INF则跳过 if (dist[i][k] INF) continue; for (int j 0; j n; j) { if (dist[i][j] dist[i][k] dist[k][j]) { dist[i][j] dist[i][k] dist[k][j]; } } } }核心要点三层循环的顺序k必须放在最外层。可以理解为“允许使用前k个节点作为中转点”。自环与重边初始化时dist[i][i]必须设为0。读入边时要处理重边取最小值dist[u][v] min(dist[u][v], w)。负权边Floyd可以处理带负权边的图但不能处理有负权环的图此时最短路无定义。4. 最小生成树算法模板最小生成树MST用于在无向连通图中找出一棵包含所有顶点、且边权之和最小的树。两种经典算法Prim适合稠密图和Kruskal适合稀疏图。4.1 Kruskal算法并查集的最佳搭档这是竞赛中最常用的MST算法思路清晰代码好写借助并查集实现。struct Edge { int u, v, w; bool operator(const Edge other) const { return w other.w; // 按边权升序排序 } }; vectorEdge edges; // 存储所有边 // 并查集模板 class DSU { vectorint parent, rank; public: DSU(int n) : parent(n), rank(n, 0) { iota(parent.begin(), parent.end(), 0); } int find(int x) { return parent[x] x ? x : parent[x] find(parent[x]); // 路径压缩 } bool unite(int x, int y) { x find(x); y find(y); if (x y) return false; // 按秩合并 if (rank[x] rank[y]) swap(x, y); parent[y] x; if (rank[x] rank[y]) rank[x]; return true; } }; int kruskal(int n) { sort(edges.begin(), edges.end()); DSU dsu(n); int mst_cost 0, edges_used 0; for (auto e : edges) { if (dsu.unite(e.u, e.v)) { mst_cost e.w; edges_used; if (edges_used n - 1) break; // 已找到n-1条边提前结束 } } return edges_used n - 1 ? mst_cost : -1; // -1表示图不连通 }经验技巧并查集优化路径压缩和按秩合并能保证近乎常数时间的查找与合并操作这是Kruskal高效的基础。提前终止当已选取的边数等于n-1时MST已经构建完成可以立即跳出循环这是一个有效的优化。判断连通性最终如果edges_used ! n-1说明原图不连通不存在MST。4.2 Prim算法与Dijkstra神似Prim算法从一个点开始逐步扩张MST集合。其实现与Dijkstra非常相似区别在于优先队列中存储的是连接到当前MST集合的最小边权而非到起点的距离。int prim(int start, int n) { vectorint minEdge(n, INF); // minEdge[i]表示节点i连接到当前MST集合的最小边权 vectorbool inMST(n, false); priority_queuepairint, int, vectorpairint, int, greater pq; minEdge[start] 0; pq.emplace(0, start); int mst_cost 0, nodes_in_mst 0; while (!pq.empty() nodes_in_mst n) { auto [w, u] pq.top(); pq.pop(); if (inMST[u]) continue; // 已在MST中跳过 inMST[u] true; mst_cost w; nodes_in_mst; for (auto [v, weight] : adj[u]) { if (!inMST[v] weight minEdge[v]) { minEdge[v] weight; pq.emplace(minEdge[v], v); } } } return nodes_in_mst n ? mst_cost : -1; }选型建议对于稀疏图边数E远小于V²使用Kruskal代码简单且排序复杂度O(E log E)占主导。对于稠密图边数E接近V²使用Prim邻接矩阵或普通二叉堆其复杂度为O(V²)优于Kruskal的O(V² log V)。在竞赛中由于图通常以稀疏图为主且Kruskal代码更易写易记我优先使用Kruskal算法。5. 拓扑排序与关键路径拓扑排序是针对有向无环图DAG的线性序列排序应用广泛如课程安排、编译顺序。关键路径则在DAG的基础上计算项目的最短完成时间。5.1 拓扑排序BFS实现也称Kahn算法这是最稳定、最常用的实现方式。vectorint topologicalSort(int n) { vectorint inDegree(n, 0); // 计算入度 for (int u 0; u n; u) { for (auto [v, _] : adj[u]) { // 如果边无权则只存邻接点 inDegree[v]; } } queueint q; for (int i 0; i n; i) { if (inDegree[i] 0) q.push(i); } vectorint topoOrder; while (!q.empty()) { int u q.front(); q.pop(); topoOrder.push_back(u); for (auto [v, _] : adj[u]) { if (--inDegree[v] 0) { q.push(v); } } } // 判断是否有环 if (topoOrder.size() ! n) { // 图中存在环无法拓扑排序 return {}; } return topoOrder; }常见问题如何判断是否有环如果最终得到的拓扑序列长度不等于顶点数n则说明有向图中存在环。字典序最小/大的拓扑序只需将队列queue替换为优先队列priority_queue即可。小顶堆得到字典序最小大顶堆得到字典序最大。5.2 关键路径基于拓扑排序关键路径的本质是在拓扑序的基础上进行两轮动态规划最早开始时间和最晚开始时间。// 假设图用邻接表存储边有权重代表活动持续时间 // edges: adj[u] { {v1, w1}, {v2, w2}, ... } pairint, vectorint criticalPath(int n) { // 1. 拓扑排序 auto topoOrder topologicalSort(n); if (topoOrder.empty()) return {-1, {}}; // 有环 // 2. 计算最早开始时间 ve (earliest start time) vectorint ve(n, 0); for (int u : topoOrder) { for (auto [v, w] : adj[u]) { ve[v] max(ve[v], ve[u] w); } } // 项目最早完成时间就是汇点的ve值。假设汇点是最后一个节点或需自己确定 int projectFinishTime *max_element(ve.begin(), ve.end()); // 3. 计算最晚开始时间 vl (latest start time) vectorint vl(n, projectFinishTime); // 逆拓扑序计算 for (auto it topoOrder.rbegin(); it ! topoOrder.rend(); it) { int u *it; for (auto [v, w] : adj[u]) { // u的最晚开始时间不能影响其所有后继v的最晚开始时间 vl[u] min(vl[u], vl[v] - w); } } // 4. 计算关键活动最早开始时间 最晚开始时间 vectorint criticalActivities; for (int u 0; u n; u) { for (auto [v, w] : adj[u]) { int e ve[u]; // 活动(u-v)的最早开始时间 int l vl[v] - w; // 活动(u-v)的最晚开始时间 if (e l) { // (u, v) 是关键活动 criticalActivities.push_back(u); // 可根据需要存储活动标识 criticalActivities.push_back(v); } } } return {projectFinishTime, criticalActivities}; }理解要点ve[i]事件i的最早发生时间等于所有前驱事件最早发生时间加上活动时间的最大值。vl[i]事件i的最晚发生时间等于所有后继事件最晚发生时间减去活动时间的最小值。关键活动对于活动(u-v)其最早开始时间e ve[u]最晚开始时间l vl[v] - w。若e l则该活动没有松弛时间是关键活动。所有关键活动组成的路径就是关键路径。6. 连通分量与Tarjan算法连通分量问题包括无向图的连通块、有向图的强连通分量SCC等。Tarjan算法是求SCC的利器其核心是一次DFS通过dfn时间戳和low能追溯到的最早栈中节点两个数组。6.1 Tarjan算法求强连通分量vectorint dfn, low, inStack; stackint stk; vectorvectorint sccs; // 存储所有SCC int timestamp 0; void tarjan(int u, const vectorvectorint adj) { // 此模板针对有向图邻接表只存点 dfn[u] low[u] timestamp; stk.push(u); inStack[u] true; for (int v : adj[u]) { if (!dfn[v]) { // v未访问 tarjan(v, adj); low[u] min(low[u], low[v]); } else if (inStack[v]) { // v在栈中说明是当前SCC的候选 low[u] min(low[u], dfn[v]); // 注意这里是dfn[v]不是low[v] } } // 如果u是当前SCC的根dfn[u] low[u] if (dfn[u] low[u]) { vectorint scc; while (true) { int v stk.top(); stk.pop(); inStack[v] false; scc.push_back(v); if (v u) break; } sccs.push_back(scc); } } // 调用方式 int n; // 顶点数 dfn.assign(n, 0); low.assign(n, 0); inStack.assign(n, false); timestamp 0; sccs.clear(); while (!stk.empty()) stk.pop(); for (int i 0; i n; i) { if (!dfn[i]) { tarjan(i, adj); } }算法精髓与易错点low[u]的更新在else if (inStack[v])分支中必须用dfn[v]来更新low[u]。用low[v]在某些情况下会导致错误如横叉边误判。栈的作用栈stk用于存放当前搜索路径上的节点inStack数组用于快速判断节点是否在栈中。当一个SCC的根被找到时将栈中直到该根的所有节点弹出它们构成一个SCC。时间戳dfndfn同时起到了vis访问标记的作用。dfn[v]0表示未访问。应用求出的SCCs可以用于缩点将有向图转化为DAG从而简化问题。6.2 并查集求无向图连通分量对于无向图求连通分量简单得多通常用并查集或DFS/BFS即可。DSU dsu(n); for (每条无向边 (u, v)) { dsu.unite(u, v); } // 之后dsu.find(i)相同的节点就在同一个连通分量中7. 模板的使用、调试与扩展7.1 如何有效记忆和使用模板死记硬背代码是低效的。我的方法是理解第一彻底搞懂每个算法的原理、步骤和时空复杂度。固定风格确定自己的代码风格如变量命名、INF取值、邻接表结构并在所有模板中保持一致。反复默写在理解的基础上脱离参考在白板或空白文件中默写代码。写完后与标准模板对比找出差异并思考原因。配套练习每个模板对应刷3-5道经典题目在应用中巩固。例如Dijkstra做“最短路计数”、“次短路”Tarjan做“校园网络”、“受欢迎的牛”。7.2 调试技巧当模板“不灵”时即使模板正确也可能因为题目细节导致错误。以下是我的调试清单图的存储是否正确检查是无向图还是有向图检查顶点编号是0-based还是1-based是否做了转换检查重边、自环是否处理得当。初始化是否到位dist数组、vis数组、inDegree数组等是否全部正确初始化INF的值是否足够大例如最短路总长可能超过1e9边界条件是否考虑起点终点相同图不连通n0或n1算法前提是否满足对Dijkstra确认没有负权边对拓扑排序确认是有向图对Prim/Kruskal确认是无向图。输出格式是否匹配要求输出路径还是仅距离如果不可达是输出-1、INF还是特定字符串7.3 模板的扩展方向基础模板掌握后可以针对特定问题扩展次短路/K短路基于Dijkstra维护到每个点的最短和次短距离。最小生成树计数基于Kruskal结合并查集与矩阵树定理。差分约束系统将其转化为图论问题用SPFA判断负环来求解。网络流基础虽然不属于严格意义上的“模板”但Dinic或ISAP算法可以作为高阶模板准备。最后记住模板是工具不是目的。真正的能力在于理解问题本质并选择或组合合适的工具去解决它。在比赛中清晰的思路和稳定的心态比死记硬背一百个模板更重要。这份“图论篇”是我个人经验的结晶希望能为你搭建一个坚实的起点但更重要的是你要在大量的练习中将其内化成自己的东西形成你自己的“第十二届模板”。
算法竞赛图论实战：从Dijkstra到Tarjan的个人模板精讲
1. 项目概述一份来自赛场的图论实战指南如果你正在备战蓝桥杯这类算法竞赛或者想系统性地提升自己的图论解题能力那么这份“个人模板”的分享或许正是你需要的。这不是一份教科书式的理论罗列而是我从第十二届蓝桥杯国赛的备赛和实战中将高频、核心的图论算法进行提炼、优化和封装后形成的“武器库”。图论问题在算法竞赛中占据着举足轻重的地位从最短路、最小生成树到拓扑排序、连通分量几乎每场比赛都会涉及。但比赛时时间紧迫现场推导并调试一个复杂算法的完整代码是不现实的。因此拥有一套经过自己反复验证、边界清晰、接口明确的模板代码是稳定发挥的关键。这份“图论篇”模板核心价值在于“实战化”和“个人化”。它不仅仅是将算法用代码实现更重要的是融入了我在刷题和比赛中积累的踩坑经验、性能优化技巧和不同场景下的适用性判断。例如Dijkstra算法何时用堆优化邻接表和邻接矩阵在什么数据规模下切换Tarjan算法求强连通分量时栈和标记数组的细节如何处理这些在标准教材中可能一笔带过但在实际编码和调试中却至关重要的问题都会在这份模板的注释和配套说明中得到解答。接下来我将逐一拆解这份模板的核心模块分享其设计思路、实现细节以及那些只有真正写过、调过、错过才能领悟的“心法”。2. 模板整体架构与设计哲学2.1 为什么需要“个人模板”很多初学者会直接从开源平台复制他人的模板这固然是快速入门的方法但存在隐患。首先你不理解其中每一个变量、每一步操作的深意调试时一旦出错将无从下手。其次别人的模板风格和习惯可能与你不同在紧张的比赛环境中使用不熟悉的代码容易增加心智负担。因此我的建议是以经典实现为蓝本在大量练习中根据自身的编码习惯和常见错误进行改造和固化最终形成肌肉记忆。我的模板设计遵循几个原则一致性所有图论算法的存储结构如邻接表保持统一减少切换成本。鲁棒性对输入数据的边界情况如负权边、自环、重边有明确的处理逻辑或注释提示。可读性关键步骤有简洁注释变量命名清晰如dist[]表示距离vis[]表示访问标记。模块化每个算法是独立的函数或类但共享基础的数据结构方便组合使用。2.2 核心数据结构选型邻接表的绝对优势在竞赛中除非题目明确给出稠密图边数接近顶点数的平方否则邻接表是唯一的选择。它节省空间遍历效率高。我的模板统一使用vector实现的邻接表对于带权图使用结构体或pair存储边。// 方式一使用vectorpairint, int first是邻接点second是边权 vectorvectorpairint, int adj(n); // 方式二定义Edge结构体可存储更多信息如边编号 struct Edge { int to, w; }; vectorvectorEdge adj(n);提示我倾向于使用方式一因为pair默认支持比较操作在放入优先队列时无需重载运算符更为简洁。仅在需要记录额外信息时才使用结构体。对于需要快速判断两点间是否有边或者需要处理边删除的特殊题目才会考虑邻接矩阵或链式前向星。链式前向星虽然空间更省但可读性稍差调试不便因此我的主模板仍以vector邻接表为主但会准备一个链式前向星的版本作为备选。3. 最短路算法模板精讲最短路是图论最核心的问题之一。模板必须覆盖三种主要场景非负权图单源最短路Dijkstra、带负权图单源最短路SPFA/Bellman-Ford、多源最短路Floyd。3.1 Dijkstra算法堆优化版竞赛中的绝对主力这是你必须熟练掌握且要写得又快又准的算法。核心是使用优先队列小顶堆不断取出当前距离起点最近的点进行松弛。// 假设图使用 vectorvectorpairint, int adj 存储 const int INF 0x3f3f3f3f; // 一个很大的数常用且两倍不会溢出int vectorint dijkstra(int start, int n) { vectorint dist(n, INF); vectorbool vis(n, false); // 可有可无用于判断是否已确定最短距离 dist[start] 0; // 优先队列pair当前距离 节点编号 priority_queuepairint, int, vectorpairint, int, greaterpairint, int pq; pq.emplace(0, start); while (!pq.empty()) { auto [d, u] pq.top(); pq.pop(); // 关键优化如果弹出的距离大于当前记录的距离说明是旧队列中的无效项直接跳过 if (d dist[u]) continue; // 如果使用了vis数组可以在这里标记vis[u]true for (auto [v, w] : adj[u]) { if (dist[v] dist[u] w) { dist[v] dist[u] w; pq.emplace(dist[v], v); } } } return dist; }实操心得与避坑指南INF的选择0x3f3f3f3f是一个魔法数字其值约为1e9且满足INF INF不会溢出32位有符号整数用memset(dist, 0x3f, sizeof dist)可以快速初始化为该值。vis数组的必要性在标准的Dijkstra教学中常用vis标记已确定最短路的点。但在堆优化版本中if (d dist[u]) continue;这行代码已经起到了同样的作用且更高效。因此vis数组可以省略简化代码。优先队列的冗余项这是最重要的优化点。当某个点u的距离被更新多次时队列中会存在多个{dist1, u},{dist2, u}... 的项。我们只处理第一个即距离最小的弹出的项后续弹出的更大距离的项通过if (d dist[u]) continue;直接跳过。这能避免大量无效操作。边权为非负这是Dijkstra算法的前提。如果图中存在负权边算法可能得出错误结果。此时必须使用SPFA或Bellman-Ford。3.2 SPFA算法虽有名声但需慎用SPFA (Shortest Path Faster Algorithm) 是Bellman-Ford的队列优化版本在随机图上效率很高但最坏时间复杂度仍为O(VE)可能被特殊数据卡超时。因此在竞赛中如果题目没有负权边一律使用Dijkstra。只有明确存在负权边或负权环时才考虑SPFA。// SPFA 判断从start点出发是否存在负权环通过记录入队次数 bool spfa(int start, int n, vectorint dist) { vectorint cnt(n, 0); // 记录入队次数 vectorbool inQueue(n, false); queueint q; dist.assign(n, INF); dist[start] 0; q.push(start); inQueue[start] true; cnt[start]; while (!q.empty()) { int u q.front(); q.pop(); inQueue[u] false; for (auto [v, w] : adj[u]) { if (dist[v] dist[u] w) { dist[v] dist[u] w; if (!inQueue[v]) { q.push(v); inQueue[v] true; cnt[v]; // 如果入队次数超过n次说明存在负权环 if (cnt[v] n) return true; } } } } return false; // 不存在从start可达的负权环 }注意事项判断负权环上述代码通过记录每个点的入队次数是否超过n来判断是否存在从起点start可达的负权环。这是SPFA的一个重要应用。性能风险在非负权图上SPFA的效率不稳定。有些出题人会特意构造网格图等数据来使SPFA退化。因此“遇事不决用Dijkstra”是更稳妥的竞赛策略。3.3 Floyd算法多源最短路的简洁之选Floyd算法基于动态规划代码极其简洁适用于顶点数不多通常n500的多源最短路问题或者需要计算任意两点间距离的场景。// 初始化dist[i][i] 0, 有边则为边权无边则为INF vectorvectorint dist(n, vectorint(n, INF)); for (int i 0; i n; i) dist[i][i] 0; // ... 读入边初始化dist[u][v] w for (int k 0; k n; k) { for (int i 0; i n; i) { // 一个小优化如果dist[i][k]已经是INF则跳过 if (dist[i][k] INF) continue; for (int j 0; j n; j) { if (dist[i][j] dist[i][k] dist[k][j]) { dist[i][j] dist[i][k] dist[k][j]; } } } }核心要点三层循环的顺序k必须放在最外层。可以理解为“允许使用前k个节点作为中转点”。自环与重边初始化时dist[i][i]必须设为0。读入边时要处理重边取最小值dist[u][v] min(dist[u][v], w)。负权边Floyd可以处理带负权边的图但不能处理有负权环的图此时最短路无定义。4. 最小生成树算法模板最小生成树MST用于在无向连通图中找出一棵包含所有顶点、且边权之和最小的树。两种经典算法Prim适合稠密图和Kruskal适合稀疏图。4.1 Kruskal算法并查集的最佳搭档这是竞赛中最常用的MST算法思路清晰代码好写借助并查集实现。struct Edge { int u, v, w; bool operator(const Edge other) const { return w other.w; // 按边权升序排序 } }; vectorEdge edges; // 存储所有边 // 并查集模板 class DSU { vectorint parent, rank; public: DSU(int n) : parent(n), rank(n, 0) { iota(parent.begin(), parent.end(), 0); } int find(int x) { return parent[x] x ? x : parent[x] find(parent[x]); // 路径压缩 } bool unite(int x, int y) { x find(x); y find(y); if (x y) return false; // 按秩合并 if (rank[x] rank[y]) swap(x, y); parent[y] x; if (rank[x] rank[y]) rank[x]; return true; } }; int kruskal(int n) { sort(edges.begin(), edges.end()); DSU dsu(n); int mst_cost 0, edges_used 0; for (auto e : edges) { if (dsu.unite(e.u, e.v)) { mst_cost e.w; edges_used; if (edges_used n - 1) break; // 已找到n-1条边提前结束 } } return edges_used n - 1 ? mst_cost : -1; // -1表示图不连通 }经验技巧并查集优化路径压缩和按秩合并能保证近乎常数时间的查找与合并操作这是Kruskal高效的基础。提前终止当已选取的边数等于n-1时MST已经构建完成可以立即跳出循环这是一个有效的优化。判断连通性最终如果edges_used ! n-1说明原图不连通不存在MST。4.2 Prim算法与Dijkstra神似Prim算法从一个点开始逐步扩张MST集合。其实现与Dijkstra非常相似区别在于优先队列中存储的是连接到当前MST集合的最小边权而非到起点的距离。int prim(int start, int n) { vectorint minEdge(n, INF); // minEdge[i]表示节点i连接到当前MST集合的最小边权 vectorbool inMST(n, false); priority_queuepairint, int, vectorpairint, int, greater pq; minEdge[start] 0; pq.emplace(0, start); int mst_cost 0, nodes_in_mst 0; while (!pq.empty() nodes_in_mst n) { auto [w, u] pq.top(); pq.pop(); if (inMST[u]) continue; // 已在MST中跳过 inMST[u] true; mst_cost w; nodes_in_mst; for (auto [v, weight] : adj[u]) { if (!inMST[v] weight minEdge[v]) { minEdge[v] weight; pq.emplace(minEdge[v], v); } } } return nodes_in_mst n ? mst_cost : -1; }选型建议对于稀疏图边数E远小于V²使用Kruskal代码简单且排序复杂度O(E log E)占主导。对于稠密图边数E接近V²使用Prim邻接矩阵或普通二叉堆其复杂度为O(V²)优于Kruskal的O(V² log V)。在竞赛中由于图通常以稀疏图为主且Kruskal代码更易写易记我优先使用Kruskal算法。5. 拓扑排序与关键路径拓扑排序是针对有向无环图DAG的线性序列排序应用广泛如课程安排、编译顺序。关键路径则在DAG的基础上计算项目的最短完成时间。5.1 拓扑排序BFS实现也称Kahn算法这是最稳定、最常用的实现方式。vectorint topologicalSort(int n) { vectorint inDegree(n, 0); // 计算入度 for (int u 0; u n; u) { for (auto [v, _] : adj[u]) { // 如果边无权则只存邻接点 inDegree[v]; } } queueint q; for (int i 0; i n; i) { if (inDegree[i] 0) q.push(i); } vectorint topoOrder; while (!q.empty()) { int u q.front(); q.pop(); topoOrder.push_back(u); for (auto [v, _] : adj[u]) { if (--inDegree[v] 0) { q.push(v); } } } // 判断是否有环 if (topoOrder.size() ! n) { // 图中存在环无法拓扑排序 return {}; } return topoOrder; }常见问题如何判断是否有环如果最终得到的拓扑序列长度不等于顶点数n则说明有向图中存在环。字典序最小/大的拓扑序只需将队列queue替换为优先队列priority_queue即可。小顶堆得到字典序最小大顶堆得到字典序最大。5.2 关键路径基于拓扑排序关键路径的本质是在拓扑序的基础上进行两轮动态规划最早开始时间和最晚开始时间。// 假设图用邻接表存储边有权重代表活动持续时间 // edges: adj[u] { {v1, w1}, {v2, w2}, ... } pairint, vectorint criticalPath(int n) { // 1. 拓扑排序 auto topoOrder topologicalSort(n); if (topoOrder.empty()) return {-1, {}}; // 有环 // 2. 计算最早开始时间 ve (earliest start time) vectorint ve(n, 0); for (int u : topoOrder) { for (auto [v, w] : adj[u]) { ve[v] max(ve[v], ve[u] w); } } // 项目最早完成时间就是汇点的ve值。假设汇点是最后一个节点或需自己确定 int projectFinishTime *max_element(ve.begin(), ve.end()); // 3. 计算最晚开始时间 vl (latest start time) vectorint vl(n, projectFinishTime); // 逆拓扑序计算 for (auto it topoOrder.rbegin(); it ! topoOrder.rend(); it) { int u *it; for (auto [v, w] : adj[u]) { // u的最晚开始时间不能影响其所有后继v的最晚开始时间 vl[u] min(vl[u], vl[v] - w); } } // 4. 计算关键活动最早开始时间 最晚开始时间 vectorint criticalActivities; for (int u 0; u n; u) { for (auto [v, w] : adj[u]) { int e ve[u]; // 活动(u-v)的最早开始时间 int l vl[v] - w; // 活动(u-v)的最晚开始时间 if (e l) { // (u, v) 是关键活动 criticalActivities.push_back(u); // 可根据需要存储活动标识 criticalActivities.push_back(v); } } } return {projectFinishTime, criticalActivities}; }理解要点ve[i]事件i的最早发生时间等于所有前驱事件最早发生时间加上活动时间的最大值。vl[i]事件i的最晚发生时间等于所有后继事件最晚发生时间减去活动时间的最小值。关键活动对于活动(u-v)其最早开始时间e ve[u]最晚开始时间l vl[v] - w。若e l则该活动没有松弛时间是关键活动。所有关键活动组成的路径就是关键路径。6. 连通分量与Tarjan算法连通分量问题包括无向图的连通块、有向图的强连通分量SCC等。Tarjan算法是求SCC的利器其核心是一次DFS通过dfn时间戳和low能追溯到的最早栈中节点两个数组。6.1 Tarjan算法求强连通分量vectorint dfn, low, inStack; stackint stk; vectorvectorint sccs; // 存储所有SCC int timestamp 0; void tarjan(int u, const vectorvectorint adj) { // 此模板针对有向图邻接表只存点 dfn[u] low[u] timestamp; stk.push(u); inStack[u] true; for (int v : adj[u]) { if (!dfn[v]) { // v未访问 tarjan(v, adj); low[u] min(low[u], low[v]); } else if (inStack[v]) { // v在栈中说明是当前SCC的候选 low[u] min(low[u], dfn[v]); // 注意这里是dfn[v]不是low[v] } } // 如果u是当前SCC的根dfn[u] low[u] if (dfn[u] low[u]) { vectorint scc; while (true) { int v stk.top(); stk.pop(); inStack[v] false; scc.push_back(v); if (v u) break; } sccs.push_back(scc); } } // 调用方式 int n; // 顶点数 dfn.assign(n, 0); low.assign(n, 0); inStack.assign(n, false); timestamp 0; sccs.clear(); while (!stk.empty()) stk.pop(); for (int i 0; i n; i) { if (!dfn[i]) { tarjan(i, adj); } }算法精髓与易错点low[u]的更新在else if (inStack[v])分支中必须用dfn[v]来更新low[u]。用low[v]在某些情况下会导致错误如横叉边误判。栈的作用栈stk用于存放当前搜索路径上的节点inStack数组用于快速判断节点是否在栈中。当一个SCC的根被找到时将栈中直到该根的所有节点弹出它们构成一个SCC。时间戳dfndfn同时起到了vis访问标记的作用。dfn[v]0表示未访问。应用求出的SCCs可以用于缩点将有向图转化为DAG从而简化问题。6.2 并查集求无向图连通分量对于无向图求连通分量简单得多通常用并查集或DFS/BFS即可。DSU dsu(n); for (每条无向边 (u, v)) { dsu.unite(u, v); } // 之后dsu.find(i)相同的节点就在同一个连通分量中7. 模板的使用、调试与扩展7.1 如何有效记忆和使用模板死记硬背代码是低效的。我的方法是理解第一彻底搞懂每个算法的原理、步骤和时空复杂度。固定风格确定自己的代码风格如变量命名、INF取值、邻接表结构并在所有模板中保持一致。反复默写在理解的基础上脱离参考在白板或空白文件中默写代码。写完后与标准模板对比找出差异并思考原因。配套练习每个模板对应刷3-5道经典题目在应用中巩固。例如Dijkstra做“最短路计数”、“次短路”Tarjan做“校园网络”、“受欢迎的牛”。7.2 调试技巧当模板“不灵”时即使模板正确也可能因为题目细节导致错误。以下是我的调试清单图的存储是否正确检查是无向图还是有向图检查顶点编号是0-based还是1-based是否做了转换检查重边、自环是否处理得当。初始化是否到位dist数组、vis数组、inDegree数组等是否全部正确初始化INF的值是否足够大例如最短路总长可能超过1e9边界条件是否考虑起点终点相同图不连通n0或n1算法前提是否满足对Dijkstra确认没有负权边对拓扑排序确认是有向图对Prim/Kruskal确认是无向图。输出格式是否匹配要求输出路径还是仅距离如果不可达是输出-1、INF还是特定字符串7.3 模板的扩展方向基础模板掌握后可以针对特定问题扩展次短路/K短路基于Dijkstra维护到每个点的最短和次短距离。最小生成树计数基于Kruskal结合并查集与矩阵树定理。差分约束系统将其转化为图论问题用SPFA判断负环来求解。网络流基础虽然不属于严格意义上的“模板”但Dinic或ISAP算法可以作为高阶模板准备。最后记住模板是工具不是目的。真正的能力在于理解问题本质并选择或组合合适的工具去解决它。在比赛中清晰的思路和稳定的心态比死记硬背一百个模板更重要。这份“图论篇”是我个人经验的结晶希望能为你搭建一个坚实的起点但更重要的是你要在大量的练习中将其内化成自己的东西形成你自己的“第十二届模板”。