每次看到“图论代码”这个词我第一反应不是算法书里那些严谨定理而是几年前一次训练赛的崩溃现场一道看似简单的单源最短路径题模板背得滚瓜烂熟结果 WA 了一个多小时。最后发现是点编号从 1 开始建图循环却从 0 开始起点的dist被当成普通点处理了。这类问题几乎每个写图论代码的人都遇过——不是不懂算法而是栽在“存储方式 边界条件 模板前提”这些代码细节上。所以这篇我打算换个聊法不堆概念直接从代码切入把刷题和工程开发里真正高频的东西讲透邻接表怎么存、DFS/BFS 怎么写才稳、拓扑排序判环、Dijkstra 的堆优化、Floyd 和 SPFA 的适用场景、并查集与 Kruskal 最小生成树。最后用一份实际样例完整跑一遍“拓扑排序 最短路”并整理一份能直接抄作业的 Bug 排查表。适合算法竞赛新手、准备面试或 CCF CSP、蓝桥杯这类认证的选手也适合项目里临时要写图算法但不想反复试错的人。1. 图的存储方式与建图代码多数 Bug 的第一现场想写对图论代码第一步不是急着背最短路模板而是先把图“存”对。存图方式选择不当后面每个算法都会写得很别扭还特别容易出边界问题。我自己见过太多人把邻接矩阵和邻接表混着用读边的时候按矩阵写遍历的时候却用邻接表的下标最后输出了一个看起来合理但完全不对的结果。1.1 邻接矩阵、邻接表、链式前向星到底怎么选先给一个一目了然的对比表存储方式空间复杂度建图复杂度遍历某点的出边典型场景邻接矩阵O(V^2)O(1)O(V)要扫一整行点少、稠密图、Floyd 全源最短路vector 邻接表O(VE)O(1)O(该点出度)非常快绝大多数题目的默认选择链式前向星O(VE)O(1)O(出度)按边编号遍历网络流、需要修改反向边权的算法邻接矩阵的优点是“任意两点之间有没有边”这个问题能 O(1) 回答但代价是要开n*n的二维数组。如果n 10000矩阵直接 1 亿个元素内存直接炸。所以邻接矩阵一般只在n 500左右时使用最典型的就是 Floyd 算法反正它本身就是 O(n^3)需要随机访问任意点对。vector 邻接表是我个人最推荐的日常方案。它用“每个顶点挂一个列表”的方式保存出边写起来直观调试时也能直接打印每个点的邻居。链式前向星在老竞赛选手的博客里出现频率很高核心是用head[u]表示顶点 u 的第一条边的编号再用next[i]指向同一起点的下一条边本质上是手动模拟了一个链表数组。它对某些特殊算法更友好但对新手而言没有明显优势普通题目直接 vector 足够。1.2 用 vector 写出最顺手的建图代码如果是无权图C 可以这样建int n, m; cin n m; vectorvectorint g(n 1); for (int i 0; i m; i) { int u, v; cin u v; g[u].push_back(v); g[v].push_back(u); // 无向图需要反向再加一次 }如果边上有权值就把存的内容从int换成pairint,intint n, m; cin n m; vectorvectorpairint,int g(n 1); for (int i 0; i m; i) { int u, v, w; cin u v w; g[u].push_back({v, w}); // g[v].push_back({u, w}); // 无向图时放开 }用 Python 写其实也差不多n, m map(int, input().split()) g [[] for _ in range(n 1)] for _ in range(m): u, v, w map(int, input().split()) g[u].append((v, w))关于下标建议一开始就约定好“点编号从 1 开始”这样数组开n1个所有点直接对应下标省去“减一”的麻烦。如果题目输入本身是 0 基那么统一在写入前把 u 和 v 各加一后面写算法时就不会总惦记偏移量。1.3 存图阶段最容易踩的三个坑第一个坑是多组测试数据没清空。有的题目会告诉你“输入包含多组数据”你如果直接在全局变量上 push_back上一组图的边就会残留下来导致边的数量翻倍、遍历结果错乱。正确做法是每组数据开头重新构造 vector或者先clear()不要只在循环里重置顶点数。第二个坑是有向图当成无向图建。无向图需要g[u].push_back(v)和g[v].push_back(u)两条边都加有向图只加一条。这两个操作一旦搞反拓扑排序会多出一堆根本没有的入度最短路也会跑出“回头路”。建完图后先打印一下邻接表用眼睛扫一遍邻居是否合理是最省事的检查方法。第三个坑和“重边”有关。题目里可能出现两条一样的边u - v权值分别是 5 和 2。这不会让程序崩溃但会干扰 Dijkstra 的松弛顺序。严格来说 Dijkstra 依然能收敛到正确结果只是堆里会多几个“过期状态”性能略受影响。如果追求稳妥读边时可以顺手取较小权值保留如果不处理也请至少知道这不是算法错误而是性能隐患。2. 遍历与拓扑排序先搞清楚图长什么样很多题图都藏得比较深你需要先“看”清图的结构才能决定下一步用什么算法。遍历和拓扑排序就是那副眼镜。BFS 能求无权图最短路径、判断连通块DFS 能枚举路径、做依赖分析拓扑排序则专门对付“谁先谁后”的依赖关系。2.1 BFS 与 DFS 的代码模板和标记技巧BFS 的核心就是队列加visited标记。一个典型的无权图最短路写法vectorint bfs(int s, const vectorvectorint g) { int n g.size() - 1; vectorint dist(n 1, -1); queueint q; dist[s] 0; q.push(s); while (!q.empty()) { int u q.front(); q.pop(); for (int v : g[u]) { if (dist[v] ! -1) continue; // 已经访问过 dist[v] dist[u] 1; q.push(v); } } return dist; }dist数组直接兼任了“访问标记”和“距离记录”两个职责比单独开一个bool vis[]优雅。这里的 -1 表示不可达因为距离不会为负。DFS 则更适合枚举路径、构造排列或者做环检测递归写法很简洁void dfs(int u, const vectorvectorint g, vectorint vis) { vis[u] 1; for (int v : g[u]) { if (!vis[v]) dfs(v, g, vis); } }这里vis用的是 0/1 标记。但在回溯类问题里你不能只标记“访问过”就不管了因为那一层递归退出后要允许其他路径再次进入同一个点。所以搜索路径时通常标记为 21 表示在当前这条路径上2 表示访问完成。这个技巧是环检测、二分图染色等问题的通用底座。2.2 Kahn 拓扑排序完整模板与判环逻辑拓扑排序用来解决“有依赖关系的任务排序”问题比如课程修读顺序、编译任务的先后关系。经典的 Kahn 算法不涉及递归写起来很少爆栈vectorint topoSort(int n, const vectorvectorint g) { vectorint indeg(n 1, 0); for (int u 1; u n; u) for (int v : g[u]) indeg[v]; queueint q; for (int i 1; i n; i) if (indeg[i] 0) q.push(i); vectorint order; while (!q.empty()) { int u q.front(); q.pop(); order.push_back(u); for (int v : g[u]) { indeg[v]--; if (indeg[v] 0) q.push(v); } } return order; }这里最关键的行是if (--indeg[v] 0) q.push(v)。为什么不是“一旦入度变小就入队”因为拓扑排序要求一个点只有在所有前驱都处理完之后才能出现。入度从 2 变成 1说明还有一个前置任务没完成入队就会破坏顺序。只有当入度减到 0也就是所有前驱都被输出过这个点才真正“解锁”。最终判断是否是有向无环图只要看order.size()是否等于n。如果小于n说明图中存在环环上的点入度永远不会降到 0。这个判断在我做的任务编排工具里非常重要——依赖图一旦有环整个流水线就不能启动。2.3 拓扑排序的实际应用与隐蔽陷阱一个常见变种是“输出字典序最小的拓扑序”。如果题目要求编号小的任务优先执行就把普通队列换成优先队列priority_queueint, vectorint, greaterint q;这在蓝桥杯、CSP 的一些题里经常出现。需要注意的是它改变的是“同一时刻多个入度为 0 点时的选择顺序”不会影响无环图的正确性但会让输出顺序更贴近业务规则。另一个很有用的技巧是用拓扑序做 DAG 上的动态规划。比如有向无环图上求最长路径可以先拓扑排序然后按拓扑序逐个松弛vectorint dp(n 1, 0); for (int u : order) { for (auto [v, w] : g[u]) { dp[v] max(dp[v], dp[u] w); } }这里“按拓扑序松弛”隐含了一个重要的点当处理到 u 时所有指向 u 的边一定都处理过了所以dp[u]已经是最终值。这就是 DAG 上 DP 比普通图简单的原因。如果遇到带环图还硬跑这个 DP值会不停更新必须用 SPFA 之类的算法处理。3. 最短路径把模板背后的“为什么”弄清楚最短路径是图论代码中出镜率最高的模块也是最容易在细节上翻车的地方。很多人会背 Dijkstra 模板但不知道if (d ! dist[u]) continue是为了什么也不清楚为什么 Floyd 要把中间节点放在最外层。这里我不只给代码也把这些“为什么”一起说清楚。3.1 Dijkstra 堆优化竞赛和面试的默认解Dijkstra 适用于边权非负的图。它的核心思想是每次从未确定的点里选一个距离最小的点把它标记为确定然后松弛它所有邻居。用优先队列实现时不需要手动写“查找最小距离”的循环const long long INF 4e18; vectorlong long dijkstra(int s, int n, const vectorvectorpairint,int g) { vectorlong long dist(n 1, INF); priority_queuepairlong long,int, vectorpairlong long,int, greaterpairlong long,int pq; dist[s] 0; pq.push({0, s}); while (!pq.empty()) { auto [d, u] pq.top(); pq.pop(); if (d ! dist[u]) continue; // 过期状态直接丢弃 for (auto [v, w] : g[u]) { long long nd d w; if (nd dist[v]) { dist[v] nd; pq.push({nd, v}); } } } return dist; }我解释一下if (d ! dist[u]) continue这行。优先队列里可能保存了很多“旧纪录”同一个点可能在若干次松弛中都入过堆。当它弹出时如果堆里的距离已经不是当前最新的最短距离说明之前某条更短路径已经把它更新过了这个旧状态没有必要再扩展下去。没有这行代码程序不一定会错但会把大量无效节点反复弹出在边数很大的图上很容易超时。这个优化本质上代替了朴素写法里的visited数组。INF为什么不用INT_MAX因为在dist[u] w这一步如果INF本身就是 int 的最大值加上一个正数就会溢出成负数导致后续判断全部乱掉。用0x3f3f3f3f或者更大的4e18配合 long long能避免这种溢出这也是很多老模板里写 0x3f 的原因。3.2 什么时候用 Floyd什么时候用 SPFAFloyd 是求所有点对之间最短路径的算法代码极其简单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要放在最外层因为 Floyd 的本质是动态规划。dist[i][j]表示“只允许经过编号前 k 个节点作为中间节点”时的最短路径。如果k放在内层i 到 j 的更新可能用到了还没处理完的 k状态含义就乱了。虽然有时候小数据跑出来碰巧是对的但只要数据变大或者路径交叉复杂就会出错。SPFA 是 Bellman-Ford 的队列优化适合处理带负权边但没有负环的图。模板如下vectorint spfa(int s, int n, const vectorvectorpairint,int g) { vectorint dist(n 1, INF); vectorbool inq(n 1, false); queueint q; dist[s] 0; q.push(s); inq[s] true; while (!q.empty()) { int u q.front(); q.pop(); inq[u] false; for (auto [v, w] : g[u]) { if (dist[v] dist[u] w) { dist[v] dist[u] w; if (!inq[v]) { q.push(v); inq[v] true; } } } } return dist; }SPFA 在随机图上表现不错但很多竞赛出题人喜欢构造数据把它卡到 O(V*E)。我的建议是能确定边权非负就无脑 Dijkstra只有在负权边或判断负环时才考虑 SPFA。判断负环可以看一个点入队次数是否超过 n如果超过说明存在可以从起点到达的负环。3.3 让最短路代码稳定的三个细节我在实际写题和评审别人代码时发现最短路问题的 Bug 高度集中。先总结最常见的三类第一是图可能不连通。Dijkstra 跑完以后终点距离可能仍然是INF此时题目如果要求输出一个特定占位符比如 -1你要在输出前判断。不要想当然认为输入一定连通。第二是点数和边数规模。如果用朴素的 O(V^2) Dijkstra到 10 万级别的点会直接超时还有不少人把dist开成int但最短路距离可能超过 2^31-1。我的习惯是看到 n 超过 1e5、边权可能累加到大数就直接用long long反正内存不会差太多。第三是读边时起点和终点看反。方向性错误在编码时很难一眼发现。我调试时会故意构造一个两条边的小图比如1 - 2权值 5然后输出 dist[1] 和 dist[2]如果 dist[1] 不是 0基本就是读边或者循环顺序写错了。4. 最小生成树与并查集面试官最爱的一对组合面试和竞赛里图论题很少单独考“请你背出 Kruskal”通常会把并查集藏在某个表面问题上。最典型的就是“给你一堆城市和可选道路问怎么修路让所有城市连通且总成本最低”这就是最小生成树。4.1 并查集模板路径压缩和按秩合并并查集本身不是一个图算法但它能高效地维护“两个点是否在同一连通块”。路径压缩后的查询几乎接近 O(1)是 Kruskal、判断环、连通块统计的基石。struct DSU { vectorint fa, sz; DSU(int n) { fa.resize(n 1); sz.resize(n 1, 1); for (int i 1; i n; i) fa[i] i; } int find(int x) { return fa[x] x ? x : fa[x] find(fa[x]); } bool unite(int a, int b) { a find(a); b find(b); if (a b) return false; if (sz[a] sz[b]) swap(a, b); fa[b] a; sz[a] sz[b]; return true; } };fa[x] x ? x : fa[x] find(fa[x])是压缩路径的关键。递归查询时直接把 x 的父节点指向根节点下一次查询就不用再重复走整条链。按秩合并让树尽量矮和路径压缩配合起来复杂度可以看作反阿克曼函数级别。这里有个小提醒unite返回false表示两个节点本来就在同一个集合。这个返回值在 Kruskal 里是核心——如果一条边的两端已经连通再加这条边就会形成环所以直接跳过。4.2 Kruskal 完整模板排序加并查集Kruskal 的思路很直白把所有边按权值从小到大排序依次尝试加入生成树如果边的两端不连通就把它加进去。直到成功加入 n-1 条边最小生成树就建好了。struct Edge { int u, v, w; bool operator(const Edge other) const { return w other.w; } }; int kruskal(int n, vectorEdge edges) { sort(edges.begin(), edges.end()); DSU dsu(n); int ans 0; int cnt 0; for (auto e : edges) { if (dsu.unite(e.u, e.v)) { ans e.w; cnt; if (cnt n - 1) break; } } return cnt n - 1 ? ans : -1; // -1 表示没法连通 }cnt n - 1这个判断不能省。如果所有边都扫完但 cnt 没到 n-1说明原图不连通不存在能覆盖所有点的生成树这时候返回 -1 才是正确的。很多题目会让你输出“最小生成树不存在”时的特殊结果忽略这个判断会导致输出一个看似合理实际错误的数。4.3 并查集不只是给 Kruskal 用的判断一张图是否存在环时除了拓扑排序也可以用并查集对无向图逐条加边如果某条边两端已经在同一个集合里就说明形成了环。这个思路在“最大生成树”“判断是否有冗余连接”里反复出现。另一个常用到的场景是离线回答连通性问题。比如给你若干次询问每次问“删掉某条边后两点是否还连通”。这类题直接在线处理很麻烦但如果把操作倒过来把“删边”变成“加边”并查集就能很自然地完成。这就是所谓“离线 倒序 并查集”的套路。这个模块看起来简单但真到 10 万级数据时一旦忘记路径压缩就可能递归太深导致栈溢出或者超时。所以我习惯把 DSU 封装成结构体所有并查集逻辑都从这里走避免在多个函数里重复写find。5. 一个实际场景串起多个算法拓扑排序 最短路实战光看模板容易眼高手低我用一个带权有向无环图的实际输入完整演示“先拉通结构再求最优解”的过程。假设我在做一个数据处理流水线每个任务之间有依赖关系边上的权值表示从上游任务到下游任务需要的等待时间。现在要判断这些依赖能否全部执行如果能执行还想知道从任务 1 到任务 6 的最小耗时。输入如下6 8 1 2 2 1 3 4 2 3 1 2 4 7 3 5 3 4 6 1 5 4 2 5 6 5第一行表示 6 个任务、8 条依赖关系接下来是u v w表示任务 u 完成后再等 w 时间才能开始任务 v。如果把这个图在纸上画出来会看到 1 指向 2 和 3 2 指向 3 和 4 3 指向 5 4 指向 6 5 指向 4 和 6 5 又指向 4所以边是 5 - 4 权值 2同时 2 - 4 权值 7。先用拓扑排序确认它没有环。计算各点入度后从入度为 0 的 1 开始队列依次能弹出 1、2、3、5、4、6最终 size 等于 6说明可以完整调度。然后跑一遍 Dijkstra起点是 1dist[6] 会从初始 INF 一步一步松弛成 9。也就是说任务 1 到任务 6 的最短可行路径是1 - 2 - 3 - 5 - 4 - 6总耗时 2 1 3 2 1 9。C 里把前面两个模板函数拼起来就好。主函数只需要负责读入、调用和输出int main() { int n, m; cin n m; vectorvectorpairint,int g(n 1); for (int i 0; i m; i) { int u, v, w; cin u v w; g[u].push_back({v, w}); } vectorint order topoSort(n, g); if ((int)order.size() ! n) { cout 依赖有环无法调度\n; return 0; } for (int i 0; i n; i) { cout order[i] (i 1 n ? \n : ); } vectorlong long dist dijkstra(1, n, g); cout dist[n] \n; return 0; }注意这里topoSort和dijkstra的参数里我都传了 g但是dijkstra里我把 n 也单独传入因为邻接表本身无法可靠地推算出顶点数量显式传参更稳妥。很多人喜欢在全局变量里省略参数代码短了但复用性变差工程上我推荐尽量封装成函数。调试这种综合样例时有个非常实用的方法先把 dist 数组整个打印出来。如果输入数据正确第一次迭代后 dist[2] 应该是 2、dist[3] 应该是 4如果输出里出现了 dist[1] 不为 0那大概率是点编号从 0 开始的问题。Python 版本同样很好写import heapq def dijkstra(n, g, s): INF 10**18 dist [INF] * (n 1) dist[s] 0 pq [(0, s)] while pq: d, u heapq.heappop(pq) if d ! dist[u]: continue for v, w in g[u]: nd d w if nd dist[v]: dist[v] nd heapq.heappush(pq, (nd, v)) return distPython 的堆默认是小根堆所以不需要像 C 那样指定greaterint。还有一点是 Python 递归深度默认只有 1000 左右如果 DFS 深度可能很大要么用 BFS/拓扑排序要么在文件开头设置sys.setrecursionlimit(1 25)。跑通之后可以再做一个实验把输入改成一个带环的图比如加上6 - 1这条边。拓扑排序的队列很快就空了但 order.size() 不等于 n代码会正确输出“依赖有环”。这就是模板里用返回值长度判断的原因——不要在 main 里额外写一个复杂的环检测函数那只是重复造轮子。6. 常见问题与调试实录这些 Bug 值得你有心理准备代码写得多了你会发现图论题的 Bug 是有套路的很多错误和算法本身没关系而是藏在读入、遍历、初始化里。我把这几年调试中反复遇到的典型问题整理成了速查表每一条背后都至少对应过一次真实翻车。症状可能原因排查方法样例不通过dist 全部是 INF起点编号和建图下标不一致打印 dist[s]检查是否为 0运行时栈溢出递归 DFS 层数太深改成 BFS或增大递归限制答案总是大一点点无向图只加了一条边检查建图代码是否有双向 push_back输出顺序不符合拓扑序要求字典序但用了普通队列换 priority_queueDijkstra 结果错误边权为负确认题目是否允许负权边多组数据输出叠加vector 没清空每组输入重新构造 gKruskal 返回不了 n-1 条边原图不连通检查是否孤立点排查时最忌讳一上来就猜。我自己的三板斧是先打印整张邻接表看看每一个顶点挂的邻居和权值是否和输入一致再打印前几轮松弛后的 dist人工模拟一遍前几步最后用一个极小的数据手算结果做对照。绝大多数逻辑错误都逃不过这轮检查。如果觉得自己“人工看图”很吃力还有个很实用的办法把样例画出来。在线图编辑器很多打开网页把节点和边摆进去就能非常直观地看到谁指向谁。你也可以用 Python 的 networkx 画图辅助确认import networkx as nx import matplotlib.pyplot as plt G nx.DiGraph() edges [ (1, 2, 2), (1, 3, 4), (2, 3, 1), (2, 4, 7), (3, 5, 3), (4, 6, 1), (5, 4, 2), (5, 6, 5) ] G.add_weighted_edges_from(edges) pos nx.spring_layout(G) nx.draw(G, pos, with_labelsTrue, node_colorlightblue) labels nx.get_edge_attributes(G, weight) nx.draw_networkx_edge_labels(G, pos, edge_labelslabels) plt.show()这张图一旦画出来很多“顺序错误”“少了条边”的问题会瞬间暴露。我调拓扑排序前几乎必先画一次样例图比眼睛盯着邻接表高效得多。我个人还有一个习惯把图论模板单独放到一个文件里并注释清楚每个函数的输入输出前提。例如 Dijkstra 旁边一定写着“边权非负编号从 1 开始”拓扑排序旁边写着“返回长度小于 n 则说明有环”。这样每次比赛或写工程代码时直接复制模板再改参数不轻易从零敲能省下大量查 Bug 的时间。模板本身并不难背真正区分熟练度的是细节多组数据记得清空方向别搞反INF 别让加法溢出拓扑判环用返回值长度Dijkstra 记得丢弃过期状态。把这些细节变成身体记忆图论题的代码阶段才算是真的过关了。