如果把C算法学习的路径画成一张路线图图论大概是很多人第一次感到“题目抽象到不知从哪下手”的地方。按理说它并不复杂——不就是把点和线组织起来做搜索、求路径、算最小代价可真正上手机写C图论模板时邻接表、堆优化、并查集这些名词叠在一起足够劝退一大半新手。我见过不少朋友刷题刷到图论就卡住卡点往往不在算法本身而在于没有先想清楚“这张图在代码里到底长什么样、每一步操作对应哪块内存”。这篇内容就围绕C图论的完整落地链路来写从建图、遍历到最短路、最小生成树、拓扑排序再到调试技巧和竞赛/面试里的高频套路适合正在入门图论、准备算法面试或者想系统补一遍C图论模板的读者。我会尽量把每个容易出错的细节都摊开讲代码直接给你能跑的版本。1. 为什么说图论是C算法路上的分水岭1.1 图论到底在研究什么图论研究的对象本质上是“一组对象以及对象之间的连接关系”。社交网络里的人和关注关系、物流网络里的仓库与运输线路、电路里的元件和导线都可以抽象成图。在C里实现图论算法时你面对的核心不是数学公式而是两个基础问题点怎么存、边怎么存然后在这个存储结构上做BFS、DFS、最短路、生成树、拓扑排序等操作。很多新手学图论最大的误区是一上来直接背Dijkstra模板但对“图”这个数据结构本身没有感觉。就好比别人给你一串城市和航线的列表你还没在地图上把航线画出来就急着算从北京到广州怎么飞最便宜——不是不能算而是每一步都要回头翻数据既慢又容易乱。所以我的建议始终是先解决存储再谈算法。1.2 C图论通常出现在哪五类场景算法竞赛/在线评测最典型的场景。输入一个点数N、边数M要求输出最短路、最小生成树、拓扑序等。数据范围能到10^5甚至10^6级别存储方式和时间复杂度直接决定过不过。大厂算法面试面试官喜欢把图论包装成“课程表安排”“网络延迟”“朋友圈关系”等现实问题。大部分题目停留在基于DFS/BFS的连通性判断、拓扑排序、单源最短路这几个范畴很少要求写特别冷门的算法。底层开发与业务建模比如游戏地图寻路、依赖关系解析、推荐系统中的用户行为图谱。C在游戏服务器、基础架构里的图应用非常多熟练建图和遍历是基本功。数据处理与分析图数据库、知识图谱的底层存储和查询很多高性能实现就是C写的需要对图算法的时间和空间复杂度有精准控制。日常工具脚本比如用C写个小工具解析项目模块之间的依赖关系判断循环依赖本质上也是图论里的环检测。在这几类场景里C相比其他语言的核心优势是可控性内存你可以自己管性能你可以压到极致STL里的容器配合起来也很顺手。图论题往往就是“数据规模大、递归深度深、运行时间紧”C正好是这些问题的解药也是这些问题的试金石。2. 建图是第一步三种主流存储方式怎么选2.1 邻接矩阵简单直接但只适合稠密图邻接矩阵用一个二维数组bool g[N][N]或int g[N][N]表示点与点之间是否有边、边的权值是多少。g[u][v]为真或权值表示存在从u到v的边。#include bits/stdc.h using namespace std; const int N 1010; int g[N][N]; // 无权图用bool有权图用int int main() { int n, m; cin n m; for (int i 0; i m; i) { int u, v, w; cin u v w; g[u][v] w; // 如果是无向图再加一行 g[v][u] w; } // 查询u和v是否有边g[u][v] ! 0 return 0; }这种方式的优点是实现简单、查询两点之间是否有边是O(1)在Floyd这类需要频繁枚举所有点对的算法里非常自然。缺点是空间是O(N²)N到10^5就直接爆内存。所以我通常只在两种情况下用邻接矩阵点的数量很小几百级别或者题目本身就要求用动态规划枚举所有点对。2.2 vector邻接表日常工作最常用的选择邻接表的核心思想是“对每个点只保存与它相连的边”。用vectorvectorint或vectorint adj[N]最直观#include bits/stdc.h using namespace std; const int N 100010; vectorpairint, int adj[N]; // first是目标点second是权值 void addEdge(int u, int v, int w) { adj[u].push_back({v, w}); } int main() { int n, m; cin n m; for (int i 0; i m; i) { int u, v, w; cin u v w; addEdge(u, v, w); addEdge(v, u, w); // 无向图时 } // 遍历点u的所有邻居 for (auto [v, w] : adj[u]) { // do something } return 0; }vector邻接表写起来舒服、调试方便内存占用是O(NM)适合绝大多数场景。它的劣势是每个push_back可能触发扩容产生一点常数开销但为了这点开销去换更复杂的存储方式多数时候不划算。我做工程或写题时如果没有特别说明首选就是它。2.3 链式前向星竞赛党的最爱如果你刷题刷到用cin读入10^5条边还要求1秒内跑完vector邻接表往往也够但如果你追求极致性能或者需要在一张图上反复动态加边链式前向星会更稳。它的本质是用数组模拟链表把每条边存成结构体节点用head[u]记录每个点的第一条边的编号然后通过next字段串联起来#include bits/stdc.h using namespace std; const int MAXN 100010; const int MAXM 200010; // 无向图边数要开两倍 struct Edge { int to, w, next; } edges[MAXM]; int head[MAXN], tot; void init() { memset(head, -1, sizeof(head)); tot 0; } void addEdge(int u, int v, int w) { edges[tot] {v, w, head[u]}; head[u] tot; } int main() { int n, m; cin n m; init(); for (int i 0; i m; i) { int u, v, w; cin u v w; addEdge(u, v, w); addEdge(v, u, w); // 无向图 } // 遍历点u的所有邻居 for (int i head[u]; i ! -1; i edges[i].next) { int v edges[i].to; int w edges[i].w; // do something } return 0; }链式前向星的优势在于内存是连续数组缓存友好加边是O(1)头插法不需要动态扩容有些题目开数组比开vector心理上更踏实。劣势是遍历时顺序是反的调试时不如vector直观。三种存储方式怎么选我一般按这个逻辑判断场景推荐存储理由N小于500需要枚举所有点对邻接矩阵实现简单支持O(1)查询稀疏图、写题为主vector邻接表可读性好够快大规模稀疏图、竞赛链式前向星性能稳定内存紧凑3. DFS与BFS先把“遍历”这件事吃透3.1 递归DFS的隐患与手写栈的时机深度优先搜索是图论算法的基础很多选手天天写递归DFS却从没想过它在极端数据下会炸栈。C的默认栈空间通常在8MB左右递归深度超过几万层就可能出现栈溢出而图论题目里一条链式图轻轻松松就是10万层递归。我举一个最典型的例子在一张无向图中判断从s出发能到达哪些点递归写法很简洁void dfs(int u) { visited[u] 1; for (int v : adj[u]) { if (!visited[v]) { dfs(v); } } }可当图退化成长链时第一次调用就直接递归10万层。这种行为在本地调试时可能没事放到评测机上就是Runtime Error。如果你坚持用递归可以手动调大栈空间比如在Linux下用ulimit -s unlimited但不是所有环境都允许。更稳妥的做法是在必要的时候改用手写栈void dfsIterative(int start) { stackint st; st.push(start); visited[start] 1; while (!st.empty()) { int u st.top(); st.pop(); for (int v : adj[u]) { if (!visited[v]) { visited[v] 1; st.push(v); } } } }注意手写栈的写法里我是在入栈的那一刻就标记visited[v]而不是在弹出时才标记。这个细节极其重要。如果等到出栈再标记同一个节点可能被多个邻居重复入栈最坏情况下栈里堆积大量重复元素算法复杂度会退化。这也是很多新手把BFS写成TLE的常见原因。3.2 BFS的层序需求与pair队列用法广度优先搜索通常用来求无权图的最短距离。它天然按“层”推进所以第一次访问到某个节点时路径一定最短。用STL队列实现很直接#include bits/stdc.h using namespace std; const int N 100010; vectorint adj[N]; int dist[N]; void bfs(int s) { memset(dist, -1, sizeof(dist)); queueint q; q.push(s); dist[s] 0; while (!q.empty()) { int u q.front(); q.pop(); for (int v : adj[u]) { if (dist[v] -1) { dist[v] dist[u] 1; q.push(v); } } } }如果题目需要记录“从起点到当前点走了几步”且边权都是1dist数组就够了。如果需要带上额外状态比如某些题目要求同时记录点的编号和当前层数可以改用queuepairint,intqueuepairint, int q; q.push({s, 0}); while (!q.empty()) { auto [u, step] q.front(); q.pop(); for (int v : adj[u]) { if (dist[v] -1) { dist[v] step 1; q.push({v, step 1}); } } }这里额外提醒一点BFS初始化时dist数组最好用-1表示“未访问”。这样做的好处是天然区分“距离为0的起点”和“没访问过的点”如果你用0表示未访问起点反而无法和其他未访问点区分还得额外引入visited数组麻烦。4. 四大经典算法在C里的落地与易错点4.1 堆优化的Dijkstrapriority_queue的第二关键字是决胜点单源最短路最常用的算法是堆优化的Dijkstra它适合边权非负的图。核心思想是每次从堆里取出当前距离最小的未确定点用它的所有出边去松弛邻居。C里一般这样写const int N 100010; vectorpairint, int adj[N]; long long dist[N]; bool done[N]; void dijkstra(int s) { memset(dist, 0x3f, sizeof(dist)); memset(done, 0, sizeof(done)); dist[s] 0; priority_queuepairlong long, int, vectorpairlong long, int, greater pq; pq.push({0, s}); while (!pq.empty()) { auto [d, u] pq.top(); pq.pop(); if (done[u]) continue; done[u] true; for (auto [v, w] : adj[u]) { if (dist[v] dist[u] w) { dist[v] dist[u] w; pq.push({dist[v], v}); } } } }这里有几个容易踩的坑第一priority_queue默认是大顶堆所以我们必须传入greater让它变成小顶堆。pair的比较规则是先比较first再比较second所以一定要把距离放在first、节点编号放在second。如果你把节点编号放前面堆会按点的编号排序而不是按距离排序算法结果完全错乱。第二memset(dist, 0x3f, sizeof(dist))是把每个字节设为0x3f这样每个int值变成0x3f3f3f3f约为10^9适合用来表示“无穷大”。但如果你用long long一个long long会被设成0x3f3f3f3f3f3f3f3f也够用不会溢出。注意不要直接把dist的初值设成INT_MAX因为后面执行dist[u] w时可能溢出变成负数。第三done[u]的跳过判断不是可选项。没有它同一个点可能被松弛多次、入堆多次虽然dist结果仍然正确但复杂度会退化。加了之后每个点只在第一次被出堆时处理一次复杂度稳定在O((NM)logN)。4.2 Floyd为什么最外层必须是kFloyd算法用来求任意两点之间的最短路实现非常短但很多人会写错循环顺序。标准写法是const int N 510; long long dist[N][N]; void floyd(int n) { for (int k 1; k n; k) { for (int i 1; i n; i) { for (int j 1; j n; j) { if (dist[i][j] dist[i][k] dist[k][j]) { dist[i][j] dist[i][k] dist[k][j]; } } } } }最外层循环是k即“允许经过编号为1到k的中间节点”。如果k放在最内层会导致处理后面节点时用到的某些状态还没被完整更新最终结果错误。Floyd的时间复杂度是O(N³)所以N超过500就要慎用。它适合处理稠密图、负权边但不能有负环、以及需要一次性求出所有点对距离的场景比如求最小环、传递闭包。4.3 Kruskal 并查集路径压缩和按秩合并不能省最小生成树最常用的算法是Kruskal把所有边按权值从小到大排序依次尝试加入生成树用并查集判断是否形成环。代码核心在并查集const int MAXM 200010; struct Edge { int u, v, w; bool operator(const Edge other) const { return w other.w; } } edges[MAXM]; int parent[MAXN], rnk[MAXN]; 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 (rnk[x] rnk[y]) swap(x, y); parent[y] x; if (rnk[x] rnk[y]) rnk[x]; return true; } void kruskal(int n, int m) { sort(edges, edges m); int cnt 0; long long total 0; for (int i 0; i m; i) { if (unite(edges[i].u, edges[i].v)) { total edges[i].w; cnt; if (cnt n - 1) break; } } if (cnt ! n - 1) { // 图不连通不存在生成树 } }路径压缩parent[x] find(parent[x])可以让查找几乎是O(1)。按秩合并则是让小树接到大树下面避免退化成长链。两者配合并查集的均摊复杂度非常低。新手容易忽略的一个点是unite函数里先find再判断如果两个点已经在同一集合直接返回false。这一步不写生成树会成环。4.4 拓扑排序入度数组与环检测拓扑排序解决的是“有向无环图的线性排列”问题经典场景是课程安排、编译依赖。它的原理很简单不断找入度为0的节点移除它并把它的所有出边邻居入度减1const int N 100010; vectorint adj[N]; int indeg[N]; vectorint topoSort(int n) { vectorint topo; 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 v : adj[u]) { indeg[v]--; if (indeg[v] 0) q.push(v); } } return topo; }最后如果topo.size() ! n说明图里有环。这个特性可以用来做环检测比如判断程序模块之间的循环依赖。注意这里入度数组在原图上的修改是临时的如果需要保留原数据可以先复制一份。另外如果题目要求“输出字典序最小的拓扑序列”把queue换成priority_queueint, vectorint, greaterint即可其他逻辑不用动。5. 图论题怎么调试可视化、对拍与读入优化5.1 输出dot格式让任意一张图变成图画图论题最大的调试痛点是“我自己建出来的图到底长什么样”。邻接表打印出来是一堆数字根本看不出结构。很多人会去搜“图论中的图如何在线绘制”其实如果你已经用C建好了图最优雅的方式是把邻接表转成Graphviz的dot文本然后扔给任意支持dot渲染的工具看图片。Graphviz是开源的图可视化工具dot是它的描述语言语法非常直观digraph G { 1 - 2; 1 - 3; 2 - 4; }在C里你只需要写一个辅助函数void printDot(const vectorvectorint adj) { cout digraph G {\n; for (int u 1; u (int)adj.size(); u) { for (int v : adj[u]) { cout u - v ;\n; } } cout }\n; }把它跑完后得到的输出粘贴到支持Graphviz的在线编辑器或者本地装上Graphviz后用命令dot -Tpng input.dot -o output.png渲染成图片。有了图片你再去看BFS/DFS的访问顺序、Dijkstra每次松弛哪条边都非常直观。我调试复杂图论题基本都靠这一招比自己盯着邻接表脑补快太多了。对于带权图还可以在dot里给边加标签1 - 2 [label5];C端输出时拼一下字符串就行。这样建出来的图边权也一眼可见。5.2 对拍验证随机生成小规模数据写完一个图论模板怎么确认它对不对最简单的办法是拿它和暴力解法对拍。比如你写了一个Dijkstra那就可以写一个Floyd作为基准在随机小图上反复比较结果。随机生成一张小图的思路mt19937 rng(random_device{}()); void genRandomGraph(int n, int m) { cout n m \n; for (int i 0; i m; i) { int u uniform_int_distributionint(1, n)(rng); int v uniform_int_distributionint(1, n)(rng); int w uniform_int_distributionint(1, 100)(rng); cout u v w \n; } }对拍的关键是数据规模不能太大N取5到10、M取10到20就够了这样暴力解法也能秒出结果。然后写个脚本或者手动跑多个随机用例比较两份代码的输出。这个习惯能帮你抓住大多数拼写错误、初始化疏漏。我把这个方法推荐给每个问我图论题怎么调的人它比反复瞪眼读代码有用得多。5.3 读入优化与运行时间控制图论题的输入规模往往很大cin不关同步的话很容易成为性能瓶颈。所以在图论代码里我一般会在main开头加这两行ios::sync_with_stdio(false); cin.tie(nullptr);这能让cin/cout的速度接近scanf/printf。如果数据量大到cin仍然吃力可以直接手写快读int read() { int x 0, f 1; char c getchar(); while (c 0 || c 9) { if (c -) f -1; c getchar(); } while (c 0 c 9) { x x * 10 c - 0; c getchar(); } return x * f; }这种底层读入在N和M都是10^6级别时优势明显。另外提醒一句如果你用了ios::sync_with_stdio(false)就别混用scanf和cin因为同步关闭后两者混合会发生未定义行为。6. 竞赛与面试经常换皮考的高频图论套路6.1 反向建图与超级源点有些题目直接按题意建图很别扭比如“给定一个有向图求所有能到达节点1的节点”。如果正向遍历需要从每个点出发去搜索复杂度高。反过来建图把边全部反向然后从节点1做一次BFS/DFS能访问到的所有点就是答案。这个“反向建图”技巧在竞赛里特别实用比如消息传递、依赖溯源这类题目经常用到。另一类常见技巧是“超级源点”。比如题目说“有多个起点求所有起点到某个终点的最短距离”你可以新建一个虚拟节点把它和所有起点连一条权值为0的边然后从虚拟节点跑一次Dijkstra本来要做多次最短路的问题就变成一次。这个思路在物流网络、多源扩散类题目里极其常见。6.2 分层图/拆点把状态变成节点有一类题目是“最多可以免费坐k次飞机求最短路”。你把每个节点拆成k1层第i层表示已经用了i次免费机会这样转移时既可以走正常的边不消耗免费次数也可以走一条权值为0的边到下一层消耗一次免费次数然后在整张分层图上跑Dijkstra。这是“分层图最短路”的经典套路。这种“把状态拆成节点”的思路本质上就是用图论的节点来表示状态组合把原问题转化成普通最短路。面试里偶尔也会考到类似变式比如带“冷却时间”“状态切换”的题目都可以用拆点思想。理解了之后你会发现图论的表达能力比想象中强得多。6.3 从裸题到变式怎么把模板变成解题能力很多人问我模板背得滚瓜烂熟为什么题目一变就不会原因是你只背了算法形态没有理解算法成立的条件。Dijkstra要求非负权BFS要求边权相等Kruskal需要排序拓扑排序只能处理DAG——脱离这些前提模板就是废纸。我建议的进阶方法是每学一个算法问自己三个问题。第一这个算法在什么条件下是对的第二它能容忍哪类变化比如权值变大、方向变化、节点带状态第三它和另一个算法的边界在哪里比如Dijkstra和SPFA、Prim和Kruskal把这三个问题想清楚再遇到看似新奇的题目其实都是在旧模板上套了一层壳。比如热搜里出现的“物流网络”本质上是带权图上的优化问题要么是最短路要么是最小生成树关键在于你识别出题目要的是“单点到单点的最小代价”还是“让所有节点连通的最小总代价”。这两个问题乍看都是“网络优化”解法完全不同。能快速区分它们就是解题能力的体现。最后分享一个我自己的习惯刷图论题不要只追求“AC了就算过”。每做完一题我会把代码里用到的存储结构、算法核心、易错点写几行注释和模板做对比。积累几十道题之后你会发现自己对图论的理解从“背模板”变成了“调结构”。这种转变才是真正越过图论这道分水岭的标志。 C++图论算法实战：从建图到最短路与最小生成树
如果把C算法学习的路径画成一张路线图图论大概是很多人第一次感到“题目抽象到不知从哪下手”的地方。按理说它并不复杂——不就是把点和线组织起来做搜索、求路径、算最小代价可真正上手机写C图论模板时邻接表、堆优化、并查集这些名词叠在一起足够劝退一大半新手。我见过不少朋友刷题刷到图论就卡住卡点往往不在算法本身而在于没有先想清楚“这张图在代码里到底长什么样、每一步操作对应哪块内存”。这篇内容就围绕C图论的完整落地链路来写从建图、遍历到最短路、最小生成树、拓扑排序再到调试技巧和竞赛/面试里的高频套路适合正在入门图论、准备算法面试或者想系统补一遍C图论模板的读者。我会尽量把每个容易出错的细节都摊开讲代码直接给你能跑的版本。1. 为什么说图论是C算法路上的分水岭1.1 图论到底在研究什么图论研究的对象本质上是“一组对象以及对象之间的连接关系”。社交网络里的人和关注关系、物流网络里的仓库与运输线路、电路里的元件和导线都可以抽象成图。在C里实现图论算法时你面对的核心不是数学公式而是两个基础问题点怎么存、边怎么存然后在这个存储结构上做BFS、DFS、最短路、生成树、拓扑排序等操作。很多新手学图论最大的误区是一上来直接背Dijkstra模板但对“图”这个数据结构本身没有感觉。就好比别人给你一串城市和航线的列表你还没在地图上把航线画出来就急着算从北京到广州怎么飞最便宜——不是不能算而是每一步都要回头翻数据既慢又容易乱。所以我的建议始终是先解决存储再谈算法。1.2 C图论通常出现在哪五类场景算法竞赛/在线评测最典型的场景。输入一个点数N、边数M要求输出最短路、最小生成树、拓扑序等。数据范围能到10^5甚至10^6级别存储方式和时间复杂度直接决定过不过。大厂算法面试面试官喜欢把图论包装成“课程表安排”“网络延迟”“朋友圈关系”等现实问题。大部分题目停留在基于DFS/BFS的连通性判断、拓扑排序、单源最短路这几个范畴很少要求写特别冷门的算法。底层开发与业务建模比如游戏地图寻路、依赖关系解析、推荐系统中的用户行为图谱。C在游戏服务器、基础架构里的图应用非常多熟练建图和遍历是基本功。数据处理与分析图数据库、知识图谱的底层存储和查询很多高性能实现就是C写的需要对图算法的时间和空间复杂度有精准控制。日常工具脚本比如用C写个小工具解析项目模块之间的依赖关系判断循环依赖本质上也是图论里的环检测。在这几类场景里C相比其他语言的核心优势是可控性内存你可以自己管性能你可以压到极致STL里的容器配合起来也很顺手。图论题往往就是“数据规模大、递归深度深、运行时间紧”C正好是这些问题的解药也是这些问题的试金石。2. 建图是第一步三种主流存储方式怎么选2.1 邻接矩阵简单直接但只适合稠密图邻接矩阵用一个二维数组bool g[N][N]或int g[N][N]表示点与点之间是否有边、边的权值是多少。g[u][v]为真或权值表示存在从u到v的边。#include bits/stdc.h using namespace std; const int N 1010; int g[N][N]; // 无权图用bool有权图用int int main() { int n, m; cin n m; for (int i 0; i m; i) { int u, v, w; cin u v w; g[u][v] w; // 如果是无向图再加一行 g[v][u] w; } // 查询u和v是否有边g[u][v] ! 0 return 0; }这种方式的优点是实现简单、查询两点之间是否有边是O(1)在Floyd这类需要频繁枚举所有点对的算法里非常自然。缺点是空间是O(N²)N到10^5就直接爆内存。所以我通常只在两种情况下用邻接矩阵点的数量很小几百级别或者题目本身就要求用动态规划枚举所有点对。2.2 vector邻接表日常工作最常用的选择邻接表的核心思想是“对每个点只保存与它相连的边”。用vectorvectorint或vectorint adj[N]最直观#include bits/stdc.h using namespace std; const int N 100010; vectorpairint, int adj[N]; // first是目标点second是权值 void addEdge(int u, int v, int w) { adj[u].push_back({v, w}); } int main() { int n, m; cin n m; for (int i 0; i m; i) { int u, v, w; cin u v w; addEdge(u, v, w); addEdge(v, u, w); // 无向图时 } // 遍历点u的所有邻居 for (auto [v, w] : adj[u]) { // do something } return 0; }vector邻接表写起来舒服、调试方便内存占用是O(NM)适合绝大多数场景。它的劣势是每个push_back可能触发扩容产生一点常数开销但为了这点开销去换更复杂的存储方式多数时候不划算。我做工程或写题时如果没有特别说明首选就是它。2.3 链式前向星竞赛党的最爱如果你刷题刷到用cin读入10^5条边还要求1秒内跑完vector邻接表往往也够但如果你追求极致性能或者需要在一张图上反复动态加边链式前向星会更稳。它的本质是用数组模拟链表把每条边存成结构体节点用head[u]记录每个点的第一条边的编号然后通过next字段串联起来#include bits/stdc.h using namespace std; const int MAXN 100010; const int MAXM 200010; // 无向图边数要开两倍 struct Edge { int to, w, next; } edges[MAXM]; int head[MAXN], tot; void init() { memset(head, -1, sizeof(head)); tot 0; } void addEdge(int u, int v, int w) { edges[tot] {v, w, head[u]}; head[u] tot; } int main() { int n, m; cin n m; init(); for (int i 0; i m; i) { int u, v, w; cin u v w; addEdge(u, v, w); addEdge(v, u, w); // 无向图 } // 遍历点u的所有邻居 for (int i head[u]; i ! -1; i edges[i].next) { int v edges[i].to; int w edges[i].w; // do something } return 0; }链式前向星的优势在于内存是连续数组缓存友好加边是O(1)头插法不需要动态扩容有些题目开数组比开vector心理上更踏实。劣势是遍历时顺序是反的调试时不如vector直观。三种存储方式怎么选我一般按这个逻辑判断场景推荐存储理由N小于500需要枚举所有点对邻接矩阵实现简单支持O(1)查询稀疏图、写题为主vector邻接表可读性好够快大规模稀疏图、竞赛链式前向星性能稳定内存紧凑3. DFS与BFS先把“遍历”这件事吃透3.1 递归DFS的隐患与手写栈的时机深度优先搜索是图论算法的基础很多选手天天写递归DFS却从没想过它在极端数据下会炸栈。C的默认栈空间通常在8MB左右递归深度超过几万层就可能出现栈溢出而图论题目里一条链式图轻轻松松就是10万层递归。我举一个最典型的例子在一张无向图中判断从s出发能到达哪些点递归写法很简洁void dfs(int u) { visited[u] 1; for (int v : adj[u]) { if (!visited[v]) { dfs(v); } } }可当图退化成长链时第一次调用就直接递归10万层。这种行为在本地调试时可能没事放到评测机上就是Runtime Error。如果你坚持用递归可以手动调大栈空间比如在Linux下用ulimit -s unlimited但不是所有环境都允许。更稳妥的做法是在必要的时候改用手写栈void dfsIterative(int start) { stackint st; st.push(start); visited[start] 1; while (!st.empty()) { int u st.top(); st.pop(); for (int v : adj[u]) { if (!visited[v]) { visited[v] 1; st.push(v); } } } }注意手写栈的写法里我是在入栈的那一刻就标记visited[v]而不是在弹出时才标记。这个细节极其重要。如果等到出栈再标记同一个节点可能被多个邻居重复入栈最坏情况下栈里堆积大量重复元素算法复杂度会退化。这也是很多新手把BFS写成TLE的常见原因。3.2 BFS的层序需求与pair队列用法广度优先搜索通常用来求无权图的最短距离。它天然按“层”推进所以第一次访问到某个节点时路径一定最短。用STL队列实现很直接#include bits/stdc.h using namespace std; const int N 100010; vectorint adj[N]; int dist[N]; void bfs(int s) { memset(dist, -1, sizeof(dist)); queueint q; q.push(s); dist[s] 0; while (!q.empty()) { int u q.front(); q.pop(); for (int v : adj[u]) { if (dist[v] -1) { dist[v] dist[u] 1; q.push(v); } } } }如果题目需要记录“从起点到当前点走了几步”且边权都是1dist数组就够了。如果需要带上额外状态比如某些题目要求同时记录点的编号和当前层数可以改用queuepairint,intqueuepairint, int q; q.push({s, 0}); while (!q.empty()) { auto [u, step] q.front(); q.pop(); for (int v : adj[u]) { if (dist[v] -1) { dist[v] step 1; q.push({v, step 1}); } } }这里额外提醒一点BFS初始化时dist数组最好用-1表示“未访问”。这样做的好处是天然区分“距离为0的起点”和“没访问过的点”如果你用0表示未访问起点反而无法和其他未访问点区分还得额外引入visited数组麻烦。4. 四大经典算法在C里的落地与易错点4.1 堆优化的Dijkstrapriority_queue的第二关键字是决胜点单源最短路最常用的算法是堆优化的Dijkstra它适合边权非负的图。核心思想是每次从堆里取出当前距离最小的未确定点用它的所有出边去松弛邻居。C里一般这样写const int N 100010; vectorpairint, int adj[N]; long long dist[N]; bool done[N]; void dijkstra(int s) { memset(dist, 0x3f, sizeof(dist)); memset(done, 0, sizeof(done)); dist[s] 0; priority_queuepairlong long, int, vectorpairlong long, int, greater pq; pq.push({0, s}); while (!pq.empty()) { auto [d, u] pq.top(); pq.pop(); if (done[u]) continue; done[u] true; for (auto [v, w] : adj[u]) { if (dist[v] dist[u] w) { dist[v] dist[u] w; pq.push({dist[v], v}); } } } }这里有几个容易踩的坑第一priority_queue默认是大顶堆所以我们必须传入greater让它变成小顶堆。pair的比较规则是先比较first再比较second所以一定要把距离放在first、节点编号放在second。如果你把节点编号放前面堆会按点的编号排序而不是按距离排序算法结果完全错乱。第二memset(dist, 0x3f, sizeof(dist))是把每个字节设为0x3f这样每个int值变成0x3f3f3f3f约为10^9适合用来表示“无穷大”。但如果你用long long一个long long会被设成0x3f3f3f3f3f3f3f3f也够用不会溢出。注意不要直接把dist的初值设成INT_MAX因为后面执行dist[u] w时可能溢出变成负数。第三done[u]的跳过判断不是可选项。没有它同一个点可能被松弛多次、入堆多次虽然dist结果仍然正确但复杂度会退化。加了之后每个点只在第一次被出堆时处理一次复杂度稳定在O((NM)logN)。4.2 Floyd为什么最外层必须是kFloyd算法用来求任意两点之间的最短路实现非常短但很多人会写错循环顺序。标准写法是const int N 510; long long dist[N][N]; void floyd(int n) { for (int k 1; k n; k) { for (int i 1; i n; i) { for (int j 1; j n; j) { if (dist[i][j] dist[i][k] dist[k][j]) { dist[i][j] dist[i][k] dist[k][j]; } } } } }最外层循环是k即“允许经过编号为1到k的中间节点”。如果k放在最内层会导致处理后面节点时用到的某些状态还没被完整更新最终结果错误。Floyd的时间复杂度是O(N³)所以N超过500就要慎用。它适合处理稠密图、负权边但不能有负环、以及需要一次性求出所有点对距离的场景比如求最小环、传递闭包。4.3 Kruskal 并查集路径压缩和按秩合并不能省最小生成树最常用的算法是Kruskal把所有边按权值从小到大排序依次尝试加入生成树用并查集判断是否形成环。代码核心在并查集const int MAXM 200010; struct Edge { int u, v, w; bool operator(const Edge other) const { return w other.w; } } edges[MAXM]; int parent[MAXN], rnk[MAXN]; 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 (rnk[x] rnk[y]) swap(x, y); parent[y] x; if (rnk[x] rnk[y]) rnk[x]; return true; } void kruskal(int n, int m) { sort(edges, edges m); int cnt 0; long long total 0; for (int i 0; i m; i) { if (unite(edges[i].u, edges[i].v)) { total edges[i].w; cnt; if (cnt n - 1) break; } } if (cnt ! n - 1) { // 图不连通不存在生成树 } }路径压缩parent[x] find(parent[x])可以让查找几乎是O(1)。按秩合并则是让小树接到大树下面避免退化成长链。两者配合并查集的均摊复杂度非常低。新手容易忽略的一个点是unite函数里先find再判断如果两个点已经在同一集合直接返回false。这一步不写生成树会成环。4.4 拓扑排序入度数组与环检测拓扑排序解决的是“有向无环图的线性排列”问题经典场景是课程安排、编译依赖。它的原理很简单不断找入度为0的节点移除它并把它的所有出边邻居入度减1const int N 100010; vectorint adj[N]; int indeg[N]; vectorint topoSort(int n) { vectorint topo; 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 v : adj[u]) { indeg[v]--; if (indeg[v] 0) q.push(v); } } return topo; }最后如果topo.size() ! n说明图里有环。这个特性可以用来做环检测比如判断程序模块之间的循环依赖。注意这里入度数组在原图上的修改是临时的如果需要保留原数据可以先复制一份。另外如果题目要求“输出字典序最小的拓扑序列”把queue换成priority_queueint, vectorint, greaterint即可其他逻辑不用动。5. 图论题怎么调试可视化、对拍与读入优化5.1 输出dot格式让任意一张图变成图画图论题最大的调试痛点是“我自己建出来的图到底长什么样”。邻接表打印出来是一堆数字根本看不出结构。很多人会去搜“图论中的图如何在线绘制”其实如果你已经用C建好了图最优雅的方式是把邻接表转成Graphviz的dot文本然后扔给任意支持dot渲染的工具看图片。Graphviz是开源的图可视化工具dot是它的描述语言语法非常直观digraph G { 1 - 2; 1 - 3; 2 - 4; }在C里你只需要写一个辅助函数void printDot(const vectorvectorint adj) { cout digraph G {\n; for (int u 1; u (int)adj.size(); u) { for (int v : adj[u]) { cout u - v ;\n; } } cout }\n; }把它跑完后得到的输出粘贴到支持Graphviz的在线编辑器或者本地装上Graphviz后用命令dot -Tpng input.dot -o output.png渲染成图片。有了图片你再去看BFS/DFS的访问顺序、Dijkstra每次松弛哪条边都非常直观。我调试复杂图论题基本都靠这一招比自己盯着邻接表脑补快太多了。对于带权图还可以在dot里给边加标签1 - 2 [label5];C端输出时拼一下字符串就行。这样建出来的图边权也一眼可见。5.2 对拍验证随机生成小规模数据写完一个图论模板怎么确认它对不对最简单的办法是拿它和暴力解法对拍。比如你写了一个Dijkstra那就可以写一个Floyd作为基准在随机小图上反复比较结果。随机生成一张小图的思路mt19937 rng(random_device{}()); void genRandomGraph(int n, int m) { cout n m \n; for (int i 0; i m; i) { int u uniform_int_distributionint(1, n)(rng); int v uniform_int_distributionint(1, n)(rng); int w uniform_int_distributionint(1, 100)(rng); cout u v w \n; } }对拍的关键是数据规模不能太大N取5到10、M取10到20就够了这样暴力解法也能秒出结果。然后写个脚本或者手动跑多个随机用例比较两份代码的输出。这个习惯能帮你抓住大多数拼写错误、初始化疏漏。我把这个方法推荐给每个问我图论题怎么调的人它比反复瞪眼读代码有用得多。5.3 读入优化与运行时间控制图论题的输入规模往往很大cin不关同步的话很容易成为性能瓶颈。所以在图论代码里我一般会在main开头加这两行ios::sync_with_stdio(false); cin.tie(nullptr);这能让cin/cout的速度接近scanf/printf。如果数据量大到cin仍然吃力可以直接手写快读int read() { int x 0, f 1; char c getchar(); while (c 0 || c 9) { if (c -) f -1; c getchar(); } while (c 0 c 9) { x x * 10 c - 0; c getchar(); } return x * f; }这种底层读入在N和M都是10^6级别时优势明显。另外提醒一句如果你用了ios::sync_with_stdio(false)就别混用scanf和cin因为同步关闭后两者混合会发生未定义行为。6. 竞赛与面试经常换皮考的高频图论套路6.1 反向建图与超级源点有些题目直接按题意建图很别扭比如“给定一个有向图求所有能到达节点1的节点”。如果正向遍历需要从每个点出发去搜索复杂度高。反过来建图把边全部反向然后从节点1做一次BFS/DFS能访问到的所有点就是答案。这个“反向建图”技巧在竞赛里特别实用比如消息传递、依赖溯源这类题目经常用到。另一类常见技巧是“超级源点”。比如题目说“有多个起点求所有起点到某个终点的最短距离”你可以新建一个虚拟节点把它和所有起点连一条权值为0的边然后从虚拟节点跑一次Dijkstra本来要做多次最短路的问题就变成一次。这个思路在物流网络、多源扩散类题目里极其常见。6.2 分层图/拆点把状态变成节点有一类题目是“最多可以免费坐k次飞机求最短路”。你把每个节点拆成k1层第i层表示已经用了i次免费机会这样转移时既可以走正常的边不消耗免费次数也可以走一条权值为0的边到下一层消耗一次免费次数然后在整张分层图上跑Dijkstra。这是“分层图最短路”的经典套路。这种“把状态拆成节点”的思路本质上就是用图论的节点来表示状态组合把原问题转化成普通最短路。面试里偶尔也会考到类似变式比如带“冷却时间”“状态切换”的题目都可以用拆点思想。理解了之后你会发现图论的表达能力比想象中强得多。6.3 从裸题到变式怎么把模板变成解题能力很多人问我模板背得滚瓜烂熟为什么题目一变就不会原因是你只背了算法形态没有理解算法成立的条件。Dijkstra要求非负权BFS要求边权相等Kruskal需要排序拓扑排序只能处理DAG——脱离这些前提模板就是废纸。我建议的进阶方法是每学一个算法问自己三个问题。第一这个算法在什么条件下是对的第二它能容忍哪类变化比如权值变大、方向变化、节点带状态第三它和另一个算法的边界在哪里比如Dijkstra和SPFA、Prim和Kruskal把这三个问题想清楚再遇到看似新奇的题目其实都是在旧模板上套了一层壳。比如热搜里出现的“物流网络”本质上是带权图上的优化问题要么是最短路要么是最小生成树关键在于你识别出题目要的是“单点到单点的最小代价”还是“让所有节点连通的最小总代价”。这两个问题乍看都是“网络优化”解法完全不同。能快速区分它们就是解题能力的体现。最后分享一个我自己的习惯刷图论题不要只追求“AC了就算过”。每做完一题我会把代码里用到的存储结构、算法核心、易错点写几行注释和模板做对比。积累几十道题之后你会发现自己对图论的理解从“背模板”变成了“调结构”。这种转变才是真正越过图论这道分水岭的标志。