1. 从“模板”说起为什么竞赛选手需要图论模板如果你参加过蓝桥杯这类算法竞赛或者正在备赛一定对“模板”这个词不陌生。它不是什么可以一键通关的作弊代码而是一个经过千锤百炼、封装了核心逻辑、边界清晰、可以直接套用的代码框架。尤其是在图论这个领域题目千变万化但底层算法就那么几个。Dijkstra求最短路Floyd处理多源最短路Prim或Kruskal构建最小生成树……这些算法的思想是固定的但如果在考场上现场推导、调试时间根本不够用。因此一个可靠的个人模板库就是你竞赛中的“武器库”。它意味着第一你对算法原理有深刻理解才能写出正确且高效的模板第二你经过了大量练习知道模板在哪些细节上容易出错比如邻接表的初始化、优先队列的比较函数、无穷大的取值第三你能根据题目要求快速对模板进行微调适配而不是从头开始。今天我就结合自己多年备赛和带学生的经验拆解一下图论中最核心的几个算法模板——Dijkstra、Floyd、Prim。我们不只讲代码怎么写更要讲清楚为什么这么写以及在实战中会遇到哪些坑。目标是让你拥有一套拿起来就能用、用起来不出错的“蓝桥杯国赛级”图论模板。2. Dijkstra算法模板单源最短路的基石与实战变形Dijkstra算法是解决边权非负的图中单源最短路径问题的绝对主力。它的核心思想是贪心每次从未确定最短路径的顶点中选取一个距离源点最近的顶点然后松弛其邻接点。2.1 标准邻接表版模板优先队列优化这是最常用、效率最高的版本时间复杂度为 O((VE)logV)其中V是顶点数E是边数。#include bits/stdc.h using namespace std; typedef pairint, int PII; // first: 距离, second: 顶点编号 const int MAXN 100010; // 根据题目最大顶点数调整 const int INF 0x3f3f3f3f; // 一个很大的数表示无穷大 vectorPII graph[MAXN]; // 邻接表graph[u] {v, w} int dist[MAXN]; // 从源点到每个点的最短距离 bool visited[MAXN]; // 标记是否已确定最短路径 void dijkstra(int start) { // 初始化 memset(dist, 0x3f, sizeof(dist)); memset(visited, false, sizeof(visited)); dist[start] 0; // 小顶堆按距离从小到大排序 priority_queuePII, vectorPII, greaterPII pq; pq.push({0, start}); while (!pq.empty()) { // 取出当前距离源点最近的点 auto [d, u] pq.top(); pq.pop(); // 重要优化如果这个点之前已经通过更短的路径处理过则跳过 // 因为优先队列里可能存了同一个点的多个不同距离 if (visited[u]) continue; visited[u] true; // 标记为已处理 // 松弛操作遍历u的所有邻接点 for (auto [v, w] : graph[u]) { if (dist[v] dist[u] w) { dist[v] dist[u] w; // 将新的距离入队注意这里允许同一个点多次入队 pq.push({dist[v], v}); } } } }核心细节与避坑指南visited数组的必要性很多人会问有了dist数组判断为什么还需要visited这是因为优先队列中可能存储了同一个节点旧的、更大的距离值。当这个旧值被弹出时其对应的dist[v]可能已经被更新得更小了。此时用visited标记可以避免用旧值进行无效的松弛操作这是一个关键的性能优化和正确性保证。无穷大INF的选择0x3f3f3f3f是一个魔法数字其值约为10^9。选择它有两个好处一是两个INF相加不会溢出int范围二是memset用0x3f填充时每个字节都是0x3f整个int恰好就是0x3f3f3f3f。绝对不要用INT_MAX因为dist[u] w可能导致溢出变成负数。邻接表的存储使用vectorpairint, int比vectorvectorint更节省空间也清晰。pair的第一个元素是目标顶点第二个是边权。优先队列的比较priority_queue默认是大顶堆我们需要小顶堆所以使用greaterPII作为比较函数。也可以自定义结构体重载运算符。2.2 常见变形与考点蓝桥杯不会只考裸的Dijkstra常见变形有求最短路径条数增加一个cnt[MAXN]数组cnt[start]1。在松弛时如果dist[v] dist[u] w则cnt[v] cnt[u]如果dist[v] dist[u] w则cnt[v] cnt[u]。记录最短路径增加一个pre[MAXN]数组在松弛成功时记录pre[v] u。最后从终点递归或迭代回溯即可得到路径。边权有零Dijkstra算法本身允许边权为0算法依然正确。多源单目标如果要求多个起点到一个终点的最短距离可以反向建图然后从终点跑一次Dijkstra。第K短路这是Dijkstra的进阶应用通常使用A*算法模板会更复杂。注意Dijkstra算法不能处理负权边。因为其贪心策略基于“当前最短路径即全局最短路径”的假设负权边会破坏这个假设。如果图中存在负权边需要使用SPFA或Bellman-Ford算法。3. Floyd算法模板全源最短路与传递闭包Floyd算法是经典的动态规划算法用于求解图中所有顶点对之间的最短路径。它的思想极其简洁对于每一对顶点(i, j)考虑是否存在一个中间顶点k使得从i到j经过k的路径比已知路径更短。3.1 标准模板与初始化#include bits/stdc.h using namespace std; const int MAXN 505; // Floyd一般用于顶点数较少的图N500 const int INF 0x3f3f3f3f; int dist[MAXN][MAXN]; // dist[i][j] 表示i到j的最短距离 int n; // 顶点数 void floyd() { // 三重循环k一定要放在最外层 for (int k 1; k n; k) { for (int i 1; i n; i) { for (int j 1; j n; j) { // 防止溢出先判断INF if (dist[i][k] ! INF dist[k][j] ! INF) { dist[i][j] min(dist[i][j], dist[i][k] dist[k][j]); } } } } } // 初始化示例 void init() { // 1. 自己到自己的距离为0 for (int i 1; i n; i) { for (int j 1; j n; j) { if (i j) dist[i][j] 0; else dist[i][j] INF; } } // 2. 读入边 // int u, v, w; // cin u v w; // dist[u][v] min(dist[u][v], w); // 注意处理重边取最小值 // 如果是无向图还需要 dist[v][u] w; }为什么k必须放在最外层这是Floyd算法最核心的理解点。动态规划的状态定义是dist[k][i][j]表示“只允许使用前k个顶点作为中间点从i到j的最短路径长度”。我们压缩了第一维用二维数组dist[i][j]在本地更新。k是阶段必须放在最外层这样才能保证在计算dist[i][j]时所有经过顶点1...k-1的路径都已经被考虑过。如果k放在内层逻辑就完全错了。3.2 算法特性与实战应用时间复杂度O(V³)因此通常只用于顶点数较少V ≤ 500的稠密图。空间复杂度O(V²)需要存储整个邻接矩阵。负权边处理Floyd可以处理带负权边的图但不能处理负权环。如果存在负权环则图中存在顶点到自身的最短距离为负数dist[i][i] 0这可以用来检测负环。传递闭包Floyd的思想可以推广到任何具有传递性的关系上。例如判断图的连通性有向图的可达性。我们定义reach[i][j]为true表示i可达j。那么核心代码变为for (int k 1; k n; k) for (int i 1; i n; i) for (int j 1; j n; j) reach[i][j] reach[i][j] || (reach[i][k] reach[k][j]);这在解决一些逻辑推理、状态可达性问题时非常有用。实战踩坑点重边处理初始化读入边时一定要用min(dist[u][v], w)因为题目可能给出多条u到v的边我们需要保留最短的那条。无穷大判断在更新dist[i][j]时必须先判断dist[i][k]和dist[k][j]是否为INF否则INF w可能导致溢出变成负数从而错误地更新dist[i][j]。顶点编号题目顶点编号可能从0开始也可能从1开始。模板中通常从1开始如果从0开始循环范围要相应调整。4. Prim算法模板最小生成树的贪心构造Prim算法用于在加权无向连通图中求最小生成树MST。其思想与Dijkstra非常相似从任意一个顶点开始每次将距离当前生成树集合最近的顶点加入集合并更新其他顶点到集合的距离。4.1 标准模板邻接矩阵版邻接矩阵版实现简单适合稠密图边数接近顶点数平方。#include bits/stdc.h using namespace std; const int MAXN 1005; const int INF 0x3f3f3f3f; int n; // 顶点数 int g[MAXN][MAXN]; // 邻接矩阵g[i][j]表示边权INF表示无边 int distToTree[MAXN]; // 每个点到当前生成树集合的最短距离 bool inMST[MAXN]; // 标记顶点是否已在生成树中 int prim() { // 初始化 memset(distToTree, 0x3f, sizeof(distToTree)); memset(inMST, false, sizeof(inMST)); // 从顶点1开始构建MST distToTree[1] 0; int totalWeight 0; // 最小生成树的总权值 // 循环n次每次加入一个顶点 for (int i 0; i n; i) { // 1. 寻找距离当前生成树最近的、还未加入的顶点 int u -1; for (int v 1; v n; v) { if (!inMST[v] (u -1 || distToTree[v] distToTree[u])) { u v; } } // 如果找不到说明图不连通对于非连通图这里需要处理 if (distToTree[u] INF) { return INF; // 返回INF表示无法构成生成树 } // 2. 将该顶点加入生成树 inMST[u] true; totalWeight distToTree[u]; // 3. 用新加入的顶点更新其他顶点到生成树集合的距离 for (int v 1; v n; v) { // 只更新不在树中且通过u可以更近到达树的点 // 注意这里是和g[u][v]比较不是和distToTree[u]相加 if (!inMST[v] g[u][v] distToTree[v]) { distToTree[v] g[u][v]; } } } return totalWeight; } // 初始化示例 void init() { memset(g, 0x3f, sizeof(g)); // 读入边 // for (int i 0; i m; i) { // int u, v, w; // cin u v w; // g[u][v] g[v][u] min(g[u][v], w); // 无向图处理重边 // } }4.2 优先队列优化版邻接表版对于稀疏图使用邻接表和优先队列可以将时间复杂度从O(V²)优化到O(E log V)类似Dijkstra。#include bits/stdc.h using namespace std; typedef pairint, int PII; // first: 到树的距离, second: 顶点编号 const int MAXN 100010; const int INF 0x3f3f3f3f; vectorPII graph[MAXN]; int distToTree[MAXN]; bool inMST[MAXN]; int prim() { memset(distToTree, 0x3f, sizeof(distToTree)); memset(inMST, false, sizeof(inMST)); distToTree[1] 0; int totalWeight 0; int nodeCount 0; // 记录已加入生成树的节点数 priority_queuePII, vectorPII, greaterPII pq; pq.push({0, 1}); while (!pq.empty() nodeCount n) { auto [d, u] pq.top(); pq.pop(); if (inMST[u]) continue; inMST[u] true; totalWeight d; nodeCount; for (auto [v, w] : graph[u]) { // Prim的核心更新的是顶点v到“整个生成树集合”的距离 // 这个距离就是v与树中某点连边的**最小权值** // 所以这里比较的是 w 和 distToTree[v] if (!inMST[v] w distToTree[v]) { distToTree[v] w; pq.push({distToTree[v], v}); } } } // 如果最终nodeCount n说明图不连通 return nodeCount n ? totalWeight : INF; }Prim vs Dijkstra一个关键区别这是最容易混淆的地方。两者代码结构很像都用了贪心和优先队列但更新的逻辑不同Dijkstra更新的是从源点到点v的路径总权值dist[v] min(dist[v], dist[u] w)。Prim更新的是点v到当前生成树集合的最小边权distToTree[v] min(distToTree[v], w)。在Prim的优先队列优化版中入队的是{w, v}这个w是边(u,v)的权值而不是累加和。理解这一点就不会把两个算法写串了。4.3 实战注意事项与Kruskal的抉择图不连通Prim算法默认从1号点开始如果图不连通算法只能生成1号点所在连通分量的最小生成树。模板中通过判断nodeCount是否等于n或distToTree[u]是否为INF来处理。更通用的做法是在发现无法选取新顶点时尝试从下一个未访问的顶点开始新的Prim计算多个连通分量的MST。重边与自环初始化时要用min处理重边。自环自己到自己的边通常对MST无意义可以忽略。Prim vs KruskalPrim适合稠密图尤其是用邻接矩阵实现的朴素版。思想是“加点法”。Kruskal适合稀疏图。思想是“加边法”需要对所有边按权值排序然后用并查集判断是否成环。代码通常比Prim更简短。选择在蓝桥杯比赛中如果顶点数少N≤500用邻接矩阵的Prim很直观。如果边数远小于顶点数平方用Kruskal或Prim的优先队列版更优。建议两个模板都掌握。5. 模板的调试、验证与内存管理有了模板不代表高枕无忧。在竞赛中如何快速验证模板的正确性以及避免低级错误同样重要。5.1 设计测试用例针对每个模板准备几个经典的测试用例包括基本功能测试简单的小图手动能算出结果。边界测试单个顶点。两个顶点一条边或多条重边。完全图边数最多。特殊数据测试边权相等。边权非常大检验INF设置是否合理。图不连通对Prim和遍历算法。负权边测试用Dijkstra测负权边应该出错用Floyd测负权边应该能运行检查结果。5.2 常见错误排查清单当程序结果不对时按以下顺序检查初始化dist、visited、graph数组是否正确初始化INF值是否足够大且安全输入处理顶点编号是从0还是1开始是无向图还是有向图有没有处理重边取min数组大小MAXN是否足够大通常开到题目最大范围5或题目最大范围*2对于链式前向星。算法逻辑Dijkstra优先队列弹出的点是否判断了visited松弛条件是否正确Floydk循环是否在最外层三重循环的起点和终点是否正确通常是1到nPrim更新distToTree时是比较边权w还是distToTree[u] w这是和Dijkstra的核心区别。输出如果结果是INF输出的是什么题目要求输出-1还是特定值5.3 内存与性能优化对于大型图蓝桥杯国赛有时会卡这个使用链式前向星这是空间效率最高的存图方式特别适合边数巨大的稀疏图。虽然写起来比vector邻接表稍复杂但能节省大量空间访问也更快。建议掌握其模板。struct Edge { int to, w, next; } edges[MAXM]; // MAXM 是最大边数 int head[MAXN], cnt; void addEdge(int u, int v, int w) { edges[cnt].to v; edges[cnt].w w; edges[cnt].next head[u]; head[u] cnt; } // 遍历u的邻接点for (int i head[u]; i; i edges[i].next)关闭流同步在C中使用cin/cout时在main函数开头加上ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);可以大幅提升输入输出效率。使用全局数组避免在函数内定义大数组可能造成栈溢出。所有大数组都定义为全局变量。谨慎使用endlendl会刷新缓冲区非常慢。输出换行时用\n。6. 从模板到解题以一道真题为例我们以一道经典的、融合了图论思想的题目类似“高僧斗法”来演示如何运用模板思维。题目抽象后本质是在一个一维棋盘上棋子移动规则固定求从初始状态到目标状态的最少步数。解题思路转化状态抽象将棋盘的每一种布局定义为一个“图”的“顶点”。边权定义如果通过一次合法移动能从布局A变成布局B那么在顶点A和B之间连一条边权为1的边。问题转化求从“初始状态顶点”到“目标状态顶点”的最短路径长度。这变成了一个边权为1的最短路问题。算法选择因为边权为1可以使用BFS。BFS在无权图中本身就是求最短路的高效算法。状态数量顶点数可能很多需要设计高效的状态表示如哈希和判重。模板化思维这里的“图”是隐式的我们用BFS来遍历。BFS也可以有模板队列管理、距离数组dist、访问标记visited、状态转移函数。核心代码框架和Dijkstra的思想一脉相承都是不断从“前沿”取出一个状态扩展其邻居更新距离。代码框架示意// 状态表示例如用字符串或整数编码 typedef string State; queueState q; unordered_mapState, int dist; // 记录到每个状态的距离 dist[startState] 0; q.push(startState); while (!q.empty()) { State cur q.front(); q.pop(); if (cur targetState) break; vectorState nextStates generateNext(cur); // 状态转移函数 for (State next : nextStates) { if (!dist.count(next)) { // 未访问过 dist[next] dist[cur] 1; q.push(next); } } } // 结果在 dist[targetState] 中若不存在则为默认值0通过这个例子可以看到所谓“图论模板”不仅仅是那几个经典算法。更重要的是一种建模能力将实际问题抽象为点、边、权值然后选择合适的算法模板BFS、Dijkstra、Floyd、Prim来解决。平时多练习这种转化比赛时才能快速破题。最后模板是死的人是活的。我建议你在理解透彻的基础上亲手将这几个模板敲上几十遍并用自己的测试数据去验证。过程中你会自然记住那些易错点。到了赛场上你才能像条件反射一样快速、准确地写出核心代码把宝贵的时间留给更难的建模和优化问题。记住最可靠的模板是刻在你脑子里的、经过自己大量实战检验的那一套。 蓝桥杯图论算法模板精讲：Dijkstra、Floyd、Prim核心实现与避坑指南
1. 从“模板”说起为什么竞赛选手需要图论模板如果你参加过蓝桥杯这类算法竞赛或者正在备赛一定对“模板”这个词不陌生。它不是什么可以一键通关的作弊代码而是一个经过千锤百炼、封装了核心逻辑、边界清晰、可以直接套用的代码框架。尤其是在图论这个领域题目千变万化但底层算法就那么几个。Dijkstra求最短路Floyd处理多源最短路Prim或Kruskal构建最小生成树……这些算法的思想是固定的但如果在考场上现场推导、调试时间根本不够用。因此一个可靠的个人模板库就是你竞赛中的“武器库”。它意味着第一你对算法原理有深刻理解才能写出正确且高效的模板第二你经过了大量练习知道模板在哪些细节上容易出错比如邻接表的初始化、优先队列的比较函数、无穷大的取值第三你能根据题目要求快速对模板进行微调适配而不是从头开始。今天我就结合自己多年备赛和带学生的经验拆解一下图论中最核心的几个算法模板——Dijkstra、Floyd、Prim。我们不只讲代码怎么写更要讲清楚为什么这么写以及在实战中会遇到哪些坑。目标是让你拥有一套拿起来就能用、用起来不出错的“蓝桥杯国赛级”图论模板。2. Dijkstra算法模板单源最短路的基石与实战变形Dijkstra算法是解决边权非负的图中单源最短路径问题的绝对主力。它的核心思想是贪心每次从未确定最短路径的顶点中选取一个距离源点最近的顶点然后松弛其邻接点。2.1 标准邻接表版模板优先队列优化这是最常用、效率最高的版本时间复杂度为 O((VE)logV)其中V是顶点数E是边数。#include bits/stdc.h using namespace std; typedef pairint, int PII; // first: 距离, second: 顶点编号 const int MAXN 100010; // 根据题目最大顶点数调整 const int INF 0x3f3f3f3f; // 一个很大的数表示无穷大 vectorPII graph[MAXN]; // 邻接表graph[u] {v, w} int dist[MAXN]; // 从源点到每个点的最短距离 bool visited[MAXN]; // 标记是否已确定最短路径 void dijkstra(int start) { // 初始化 memset(dist, 0x3f, sizeof(dist)); memset(visited, false, sizeof(visited)); dist[start] 0; // 小顶堆按距离从小到大排序 priority_queuePII, vectorPII, greaterPII pq; pq.push({0, start}); while (!pq.empty()) { // 取出当前距离源点最近的点 auto [d, u] pq.top(); pq.pop(); // 重要优化如果这个点之前已经通过更短的路径处理过则跳过 // 因为优先队列里可能存了同一个点的多个不同距离 if (visited[u]) continue; visited[u] true; // 标记为已处理 // 松弛操作遍历u的所有邻接点 for (auto [v, w] : graph[u]) { if (dist[v] dist[u] w) { dist[v] dist[u] w; // 将新的距离入队注意这里允许同一个点多次入队 pq.push({dist[v], v}); } } } }核心细节与避坑指南visited数组的必要性很多人会问有了dist数组判断为什么还需要visited这是因为优先队列中可能存储了同一个节点旧的、更大的距离值。当这个旧值被弹出时其对应的dist[v]可能已经被更新得更小了。此时用visited标记可以避免用旧值进行无效的松弛操作这是一个关键的性能优化和正确性保证。无穷大INF的选择0x3f3f3f3f是一个魔法数字其值约为10^9。选择它有两个好处一是两个INF相加不会溢出int范围二是memset用0x3f填充时每个字节都是0x3f整个int恰好就是0x3f3f3f3f。绝对不要用INT_MAX因为dist[u] w可能导致溢出变成负数。邻接表的存储使用vectorpairint, int比vectorvectorint更节省空间也清晰。pair的第一个元素是目标顶点第二个是边权。优先队列的比较priority_queue默认是大顶堆我们需要小顶堆所以使用greaterPII作为比较函数。也可以自定义结构体重载运算符。2.2 常见变形与考点蓝桥杯不会只考裸的Dijkstra常见变形有求最短路径条数增加一个cnt[MAXN]数组cnt[start]1。在松弛时如果dist[v] dist[u] w则cnt[v] cnt[u]如果dist[v] dist[u] w则cnt[v] cnt[u]。记录最短路径增加一个pre[MAXN]数组在松弛成功时记录pre[v] u。最后从终点递归或迭代回溯即可得到路径。边权有零Dijkstra算法本身允许边权为0算法依然正确。多源单目标如果要求多个起点到一个终点的最短距离可以反向建图然后从终点跑一次Dijkstra。第K短路这是Dijkstra的进阶应用通常使用A*算法模板会更复杂。注意Dijkstra算法不能处理负权边。因为其贪心策略基于“当前最短路径即全局最短路径”的假设负权边会破坏这个假设。如果图中存在负权边需要使用SPFA或Bellman-Ford算法。3. Floyd算法模板全源最短路与传递闭包Floyd算法是经典的动态规划算法用于求解图中所有顶点对之间的最短路径。它的思想极其简洁对于每一对顶点(i, j)考虑是否存在一个中间顶点k使得从i到j经过k的路径比已知路径更短。3.1 标准模板与初始化#include bits/stdc.h using namespace std; const int MAXN 505; // Floyd一般用于顶点数较少的图N500 const int INF 0x3f3f3f3f; int dist[MAXN][MAXN]; // dist[i][j] 表示i到j的最短距离 int n; // 顶点数 void floyd() { // 三重循环k一定要放在最外层 for (int k 1; k n; k) { for (int i 1; i n; i) { for (int j 1; j n; j) { // 防止溢出先判断INF if (dist[i][k] ! INF dist[k][j] ! INF) { dist[i][j] min(dist[i][j], dist[i][k] dist[k][j]); } } } } } // 初始化示例 void init() { // 1. 自己到自己的距离为0 for (int i 1; i n; i) { for (int j 1; j n; j) { if (i j) dist[i][j] 0; else dist[i][j] INF; } } // 2. 读入边 // int u, v, w; // cin u v w; // dist[u][v] min(dist[u][v], w); // 注意处理重边取最小值 // 如果是无向图还需要 dist[v][u] w; }为什么k必须放在最外层这是Floyd算法最核心的理解点。动态规划的状态定义是dist[k][i][j]表示“只允许使用前k个顶点作为中间点从i到j的最短路径长度”。我们压缩了第一维用二维数组dist[i][j]在本地更新。k是阶段必须放在最外层这样才能保证在计算dist[i][j]时所有经过顶点1...k-1的路径都已经被考虑过。如果k放在内层逻辑就完全错了。3.2 算法特性与实战应用时间复杂度O(V³)因此通常只用于顶点数较少V ≤ 500的稠密图。空间复杂度O(V²)需要存储整个邻接矩阵。负权边处理Floyd可以处理带负权边的图但不能处理负权环。如果存在负权环则图中存在顶点到自身的最短距离为负数dist[i][i] 0这可以用来检测负环。传递闭包Floyd的思想可以推广到任何具有传递性的关系上。例如判断图的连通性有向图的可达性。我们定义reach[i][j]为true表示i可达j。那么核心代码变为for (int k 1; k n; k) for (int i 1; i n; i) for (int j 1; j n; j) reach[i][j] reach[i][j] || (reach[i][k] reach[k][j]);这在解决一些逻辑推理、状态可达性问题时非常有用。实战踩坑点重边处理初始化读入边时一定要用min(dist[u][v], w)因为题目可能给出多条u到v的边我们需要保留最短的那条。无穷大判断在更新dist[i][j]时必须先判断dist[i][k]和dist[k][j]是否为INF否则INF w可能导致溢出变成负数从而错误地更新dist[i][j]。顶点编号题目顶点编号可能从0开始也可能从1开始。模板中通常从1开始如果从0开始循环范围要相应调整。4. Prim算法模板最小生成树的贪心构造Prim算法用于在加权无向连通图中求最小生成树MST。其思想与Dijkstra非常相似从任意一个顶点开始每次将距离当前生成树集合最近的顶点加入集合并更新其他顶点到集合的距离。4.1 标准模板邻接矩阵版邻接矩阵版实现简单适合稠密图边数接近顶点数平方。#include bits/stdc.h using namespace std; const int MAXN 1005; const int INF 0x3f3f3f3f; int n; // 顶点数 int g[MAXN][MAXN]; // 邻接矩阵g[i][j]表示边权INF表示无边 int distToTree[MAXN]; // 每个点到当前生成树集合的最短距离 bool inMST[MAXN]; // 标记顶点是否已在生成树中 int prim() { // 初始化 memset(distToTree, 0x3f, sizeof(distToTree)); memset(inMST, false, sizeof(inMST)); // 从顶点1开始构建MST distToTree[1] 0; int totalWeight 0; // 最小生成树的总权值 // 循环n次每次加入一个顶点 for (int i 0; i n; i) { // 1. 寻找距离当前生成树最近的、还未加入的顶点 int u -1; for (int v 1; v n; v) { if (!inMST[v] (u -1 || distToTree[v] distToTree[u])) { u v; } } // 如果找不到说明图不连通对于非连通图这里需要处理 if (distToTree[u] INF) { return INF; // 返回INF表示无法构成生成树 } // 2. 将该顶点加入生成树 inMST[u] true; totalWeight distToTree[u]; // 3. 用新加入的顶点更新其他顶点到生成树集合的距离 for (int v 1; v n; v) { // 只更新不在树中且通过u可以更近到达树的点 // 注意这里是和g[u][v]比较不是和distToTree[u]相加 if (!inMST[v] g[u][v] distToTree[v]) { distToTree[v] g[u][v]; } } } return totalWeight; } // 初始化示例 void init() { memset(g, 0x3f, sizeof(g)); // 读入边 // for (int i 0; i m; i) { // int u, v, w; // cin u v w; // g[u][v] g[v][u] min(g[u][v], w); // 无向图处理重边 // } }4.2 优先队列优化版邻接表版对于稀疏图使用邻接表和优先队列可以将时间复杂度从O(V²)优化到O(E log V)类似Dijkstra。#include bits/stdc.h using namespace std; typedef pairint, int PII; // first: 到树的距离, second: 顶点编号 const int MAXN 100010; const int INF 0x3f3f3f3f; vectorPII graph[MAXN]; int distToTree[MAXN]; bool inMST[MAXN]; int prim() { memset(distToTree, 0x3f, sizeof(distToTree)); memset(inMST, false, sizeof(inMST)); distToTree[1] 0; int totalWeight 0; int nodeCount 0; // 记录已加入生成树的节点数 priority_queuePII, vectorPII, greaterPII pq; pq.push({0, 1}); while (!pq.empty() nodeCount n) { auto [d, u] pq.top(); pq.pop(); if (inMST[u]) continue; inMST[u] true; totalWeight d; nodeCount; for (auto [v, w] : graph[u]) { // Prim的核心更新的是顶点v到“整个生成树集合”的距离 // 这个距离就是v与树中某点连边的**最小权值** // 所以这里比较的是 w 和 distToTree[v] if (!inMST[v] w distToTree[v]) { distToTree[v] w; pq.push({distToTree[v], v}); } } } // 如果最终nodeCount n说明图不连通 return nodeCount n ? totalWeight : INF; }Prim vs Dijkstra一个关键区别这是最容易混淆的地方。两者代码结构很像都用了贪心和优先队列但更新的逻辑不同Dijkstra更新的是从源点到点v的路径总权值dist[v] min(dist[v], dist[u] w)。Prim更新的是点v到当前生成树集合的最小边权distToTree[v] min(distToTree[v], w)。在Prim的优先队列优化版中入队的是{w, v}这个w是边(u,v)的权值而不是累加和。理解这一点就不会把两个算法写串了。4.3 实战注意事项与Kruskal的抉择图不连通Prim算法默认从1号点开始如果图不连通算法只能生成1号点所在连通分量的最小生成树。模板中通过判断nodeCount是否等于n或distToTree[u]是否为INF来处理。更通用的做法是在发现无法选取新顶点时尝试从下一个未访问的顶点开始新的Prim计算多个连通分量的MST。重边与自环初始化时要用min处理重边。自环自己到自己的边通常对MST无意义可以忽略。Prim vs KruskalPrim适合稠密图尤其是用邻接矩阵实现的朴素版。思想是“加点法”。Kruskal适合稀疏图。思想是“加边法”需要对所有边按权值排序然后用并查集判断是否成环。代码通常比Prim更简短。选择在蓝桥杯比赛中如果顶点数少N≤500用邻接矩阵的Prim很直观。如果边数远小于顶点数平方用Kruskal或Prim的优先队列版更优。建议两个模板都掌握。5. 模板的调试、验证与内存管理有了模板不代表高枕无忧。在竞赛中如何快速验证模板的正确性以及避免低级错误同样重要。5.1 设计测试用例针对每个模板准备几个经典的测试用例包括基本功能测试简单的小图手动能算出结果。边界测试单个顶点。两个顶点一条边或多条重边。完全图边数最多。特殊数据测试边权相等。边权非常大检验INF设置是否合理。图不连通对Prim和遍历算法。负权边测试用Dijkstra测负权边应该出错用Floyd测负权边应该能运行检查结果。5.2 常见错误排查清单当程序结果不对时按以下顺序检查初始化dist、visited、graph数组是否正确初始化INF值是否足够大且安全输入处理顶点编号是从0还是1开始是无向图还是有向图有没有处理重边取min数组大小MAXN是否足够大通常开到题目最大范围5或题目最大范围*2对于链式前向星。算法逻辑Dijkstra优先队列弹出的点是否判断了visited松弛条件是否正确Floydk循环是否在最外层三重循环的起点和终点是否正确通常是1到nPrim更新distToTree时是比较边权w还是distToTree[u] w这是和Dijkstra的核心区别。输出如果结果是INF输出的是什么题目要求输出-1还是特定值5.3 内存与性能优化对于大型图蓝桥杯国赛有时会卡这个使用链式前向星这是空间效率最高的存图方式特别适合边数巨大的稀疏图。虽然写起来比vector邻接表稍复杂但能节省大量空间访问也更快。建议掌握其模板。struct Edge { int to, w, next; } edges[MAXM]; // MAXM 是最大边数 int head[MAXN], cnt; void addEdge(int u, int v, int w) { edges[cnt].to v; edges[cnt].w w; edges[cnt].next head[u]; head[u] cnt; } // 遍历u的邻接点for (int i head[u]; i; i edges[i].next)关闭流同步在C中使用cin/cout时在main函数开头加上ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);可以大幅提升输入输出效率。使用全局数组避免在函数内定义大数组可能造成栈溢出。所有大数组都定义为全局变量。谨慎使用endlendl会刷新缓冲区非常慢。输出换行时用\n。6. 从模板到解题以一道真题为例我们以一道经典的、融合了图论思想的题目类似“高僧斗法”来演示如何运用模板思维。题目抽象后本质是在一个一维棋盘上棋子移动规则固定求从初始状态到目标状态的最少步数。解题思路转化状态抽象将棋盘的每一种布局定义为一个“图”的“顶点”。边权定义如果通过一次合法移动能从布局A变成布局B那么在顶点A和B之间连一条边权为1的边。问题转化求从“初始状态顶点”到“目标状态顶点”的最短路径长度。这变成了一个边权为1的最短路问题。算法选择因为边权为1可以使用BFS。BFS在无权图中本身就是求最短路的高效算法。状态数量顶点数可能很多需要设计高效的状态表示如哈希和判重。模板化思维这里的“图”是隐式的我们用BFS来遍历。BFS也可以有模板队列管理、距离数组dist、访问标记visited、状态转移函数。核心代码框架和Dijkstra的思想一脉相承都是不断从“前沿”取出一个状态扩展其邻居更新距离。代码框架示意// 状态表示例如用字符串或整数编码 typedef string State; queueState q; unordered_mapState, int dist; // 记录到每个状态的距离 dist[startState] 0; q.push(startState); while (!q.empty()) { State cur q.front(); q.pop(); if (cur targetState) break; vectorState nextStates generateNext(cur); // 状态转移函数 for (State next : nextStates) { if (!dist.count(next)) { // 未访问过 dist[next] dist[cur] 1; q.push(next); } } } // 结果在 dist[targetState] 中若不存在则为默认值0通过这个例子可以看到所谓“图论模板”不仅仅是那几个经典算法。更重要的是一种建模能力将实际问题抽象为点、边、权值然后选择合适的算法模板BFS、Dijkstra、Floyd、Prim来解决。平时多练习这种转化比赛时才能快速破题。最后模板是死的人是活的。我建议你在理解透彻的基础上亲手将这几个模板敲上几十遍并用自己的测试数据去验证。过程中你会自然记住那些易错点。到了赛场上你才能像条件反射一样快速、准确地写出核心代码把宝贵的时间留给更难的建模和优化问题。记住最可靠的模板是刻在你脑子里的、经过自己大量实战检验的那一套。