1. 项目概述：一份来自赛场的图论实战指南
如果你正在备战蓝桥杯这类算法竞赛，或者想系统性地提升自己的图论解题能力，那么这份“个人模板”的分享，或许正是你需要的。这不是一份教科书式的理论罗列，而是我从第十二届蓝桥杯国赛的备赛和实战中，将高频、核心的图论算法进行提炼、优化和封装后形成的“武器库”。图论问题在算法竞赛中占据着举足轻重的地位，从最短路、最小生成树到拓扑排序、连通分量，几乎每场比赛都会涉及。但比赛时时间紧迫，现场推导并调试一个复杂算法的完整代码是不现实的。因此，拥有一套经过自己反复验证、边界清晰、接口明确的模板代码，是稳定发挥的关键。
这份“图论篇”模板，核心价值在于“实战化”和“个人化”。它不仅仅是将算法用代码实现，更重要的是融入了我在刷题和比赛中积累的踩坑经验、性能优化技巧和不同场景下的适用性判断。例如，Dijkstra算法何时用堆优化？邻接表和邻接矩阵在什么数据规模下切换？Tarjan算法求强连通分量时，栈和标记数组的细节如何处理？这些在标准教材中可能一笔带过，但在实际编码和调试中却至关重要的问题，都会在这份模板的注释和配套说明中得到解答。接下来，我将逐一拆解这份模板的核心模块，分享其设计思路、实现细节以及那些只有真正写过、调过、错过才能领悟的“心法”。
2. 模板整体架构与设计哲学
2.1 为什么需要“个人模板”？
很多初学者会直接从开源平台复制他人的模板，这固然是快速入门的方法，但存在隐患。首先，你不理解其中每一个变量、每一步操作的深意，调试时一旦出错将无从下手。其次，别人的模板风格和习惯可能与你不同，在紧张的比赛环境中，使用不熟悉的代码容易增加心智负担。因此，我的建议是：以经典实现为蓝本，在大量练习中，根据自身的编码习惯和常见错误，进行改造和固化，最终形成肌肉记忆。
我的模板设计遵循几个原则：
- 一致性：所有图论算法的存储结构（如邻接表）保持统一，减少切换成本。
- 鲁棒性：对输入数据的边界情况（如负权边、自环、重边）有明确的处理逻辑或注释提示。
- 可读性：关键步骤有简洁注释，变量命名清晰（如
dist[]表示距离，vis[]表示访问标记）。 - 模块化：每个算法是独立的函数或类，但共享基础的数据结构，方便组合使用。
2.2 核心数据结构选型：邻接表的绝对优势
在竞赛中，除非题目明确给出稠密图（边数接近顶点数的平方），否则邻接表是唯一的选择。它节省空间，遍历效率高。我的模板统一使用vector实现的邻接表，对于带权图，使用结构体或pair存储边。
// 方式一：使用vector<pair<int, int>>， first是邻接点，second是边权 vector<vector<pair<int, int>>> adj(n); // 方式二：定义Edge结构体，可存储更多信息（如边编号） struct Edge { int to, w; }; vector<vector<Edge>> adj(n);提示：我倾向于使用方式一，因为
pair默认支持比较操作，在放入优先队列时无需重载运算符，更为简洁。仅在需要记录额外信息时才使用结构体。
对于需要快速判断两点间是否有边，或者需要处理边删除的特殊题目，才会考虑邻接矩阵或链式前向星。链式前向星虽然空间更省，但可读性稍差，调试不便，因此我的主模板仍以vector邻接表为主，但会准备一个链式前向星的版本作为备选。
3. 最短路算法模板精讲
最短路是图论最核心的问题之一。模板必须覆盖三种主要场景：非负权图单源最短路（Dijkstra）、带负权图单源最短路（SPFA/Bellman-Ford）、多源最短路（Floyd）。
3.1 Dijkstra算法（堆优化版）：竞赛中的绝对主力
这是你必须熟练掌握，且要写得又快又准的算法。核心是使用优先队列（小顶堆）不断取出当前距离起点最近的点进行松弛。
// 假设图使用 vector<vector<pair<int, int>>> adj 存储 const int INF = 0x3f3f3f3f; // 一个很大的数，常用且两倍不会溢出int vector<int> dijkstra(int start, int n) { vector<int> dist(n, INF); vector<bool> vis(n, false); // 可有可无，用于判断是否已确定最短距离 dist[start] = 0; // 优先队列，pair<当前距离， 节点编号> priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, 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, vector<int>& dist) { vector<int> cnt(n, 0); // 记录入队次数 vector<bool> inQueue(n, false); queue<int> 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算法基于动态规划，代码极其简洁，适用于顶点数不多（通常n<500）的多源最短路问题，或者需要计算任意两点间距离的场景。
// 初始化：dist[i][i] = 0, 有边则为边权，无边则为INF vector<vector<int>> dist(n, vector<int>(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; // 按边权升序排序 } }; vector<Edge> edges; // 存储所有边 // 并查集模板 class DSU { vector<int> 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) { vector<int> minEdge(n, INF); // minEdge[i]表示节点i连接到当前MST集合的最小边权 vector<bool> inMST(n, false); priority_queue<pair<int, int>, vector<pair<int, 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算法）
这是最稳定、最常用的实现方式。
vector<int> topologicalSort(int n) { vector<int> inDegree(n, 0); // 计算入度 for (int u = 0; u < n; ++u) { for (auto &[v, _] : adj[u]) { // 如果边无权，则只存邻接点 inDegree[v]++; } } queue<int> q; for (int i = 0; i < n; ++i) { if (inDegree[i] == 0) q.push(i); } vector<int> 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}, ... } pair<int, vector<int>> criticalPath(int n) { // 1. 拓扑排序 auto topoOrder = topologicalSort(n); if (topoOrder.empty()) return {-1, {}}; // 有环 // 2. 计算最早开始时间 ve (earliest start time) vector<int> 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) vector<int> 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. 计算关键活动（最早开始时间 == 最晚开始时间） vector<int> 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算法求强连通分量
vector<int> dfn, low, inStack; stack<int> stk; vector<vector<int>> sccs; // 存储所有SCC int timestamp = 0; void tarjan(int u, const vector<vector<int>>& 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]) { vector<int> 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。 - 时间戳
dfn：dfn同时起到了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）？ - 边界条件是否考虑？起点终点相同？图不连通？n=0或n=1？
- 算法前提是否满足？对Dijkstra，确认没有负权边；对拓扑排序，确认是有向图；对Prim/Kruskal，确认是无向图。
- 输出格式是否匹配？要求输出路径还是仅距离？如果不可达，是输出-1、INF还是特定字符串？
7.3 模板的扩展方向
基础模板掌握后，可以针对特定问题扩展：
- 次短路/K短路：基于Dijkstra，维护到每个点的最短和次短距离。
- 最小生成树计数：基于Kruskal，结合并查集与矩阵树定理。
- 差分约束系统：将其转化为图论问题，用SPFA判断负环来求解。
- 网络流基础：虽然不属于严格意义上的“模板”，但Dinic或ISAP算法可以作为高阶模板准备。
最后，记住模板是工具，不是目的。真正的能力在于理解问题本质，并选择或组合合适的工具去解决它。在比赛中，清晰的思路和稳定的心态，比死记硬背一百个模板更重要。这份“图论篇”是我个人经验的结晶，希望能为你搭建一个坚实的起点，但更重要的是，你要在大量的练习中，将其内化成自己的东西，形成你自己的“第十二届模板”。
