每次遇到图论题里vectorvectorint存邻接表被卡到怀疑人生的时候我都会想起最开始学“边表法”那个下午。这东西在打竞赛的人嘴里很常见换个名字叫“链式前向星”说透了其实就是用一坨连续数组模拟链表来存图。很多新手一听“模拟链表”就发怵觉得没必要但等你真遇到千万级数据、递归建图、反向边成对修改这种场景就知道边表法有多香了。这篇文章不打算绕弯子直接用配合代码的方式把边表法从头到尾拆一遍包括它为什么省内存、为什么遍历快、建图的时候各个数组到底在干嘛以及新手最容易踩的几个坑。不管你是刚接触图论的初学者还是已经用 vector 存图但想再提升一下性能的进阶选手这篇都能给你一些能用上的东西。1. 存图方式对比为什么老手偏爱边表法1.1 三种常见存图方案的本质区别先花两分钟把常见的三种存图方式捋清楚不然你根本体会不到边表法的好处。第一种是邻接矩阵开一个int mp[N][N]mp[i][j]直接记录点 i 到点 j 的权值。它最大的优点是好写但缺点也致命空间是 O(V^2) 的V 到 1e5 的时候就彻底炸了而且遍历一个点的所有邻接点要扫一整行复杂度 O(V)在稀疏图里纯属浪费。第二种是用vectorint G[N]或者vectorpairint,int的邻接表这也是很多教材和网课默认教的方式。插入边的时候G[u].push_back(v)写起来挺舒服代码也确实直观。但它的问题是每次 push_back 都可能触发动态扩容、重新分配内存如果你没提前 reserve大量加边时会有不少额外开销而且 vector 本身的头指针、size、capacity 这些元数据存在不同地方cache 命中率也不会好到哪去。第三种就是本文的主角边表法很多 OI 圈选手干脆叫它链式前向星。它本质上是用数组模拟一个“头插法”的链表head[u] 存的是点 u 的第一条边在数组里的下标然后每条边里存 next指向的是同一起点 u 的上一条边。这样一来你新增一条边只需要往一个全局数组末尾追加边再改一下 head[u] 就行整个过程没有任何动态扩容也不存在内存碎片。1.2 什么时候该用边表法如果你的图规模不大几百几千个点用 vector 完全没问题我不劝你非换边表法不可。但下面这几种场景边表法的优势就特别明显了图特别大N 和 M 数量级到 1e5、1e6vector 反复扩容带来的时间开销很可观边表基本上是一步到位。递归遍历多比如树形 DP、深搜找环、Tarjan 系列算法边表法建出来的图“链”很规整递归访问顺序稳定不容易碰到异常情况。需要成对操作反向边比如网络流里的增广路算法经常要动态修改正向边和反向边容量边表法可以把一对反向边放在相邻下标上用i ^ 1快速定位vector 其实也能做但不那么顺手。数据范围要求内存卡得很死vector 每个元素有额外开销边表法就是纯粹几条大数组省得不是一星半点。我在实际做题里的体会是如果题目给了个 2e5 个点、1e6 条边的图用 vector 存完再跑一遍 Tarjan大概率能过但总有点提心吊胆换了边表法之后光是建图阶段就快了不少跑递归心里也踏实。这属于那种“关键时刻救你一条命”的数据结构。2. 核心设计四个数组和一条插入语句2.1 head、to、nxt、val 分别干什么边表法的核心数据结构特别简单一般开四个数组就够用了。const int MAXN 100005; const int MAXM 200005; // 注意无向图要开两倍 int head[MAXN]; // head[u] 表示点 u 最近插入的一条边在数组中的下标0 表示无边 int to[MAXM]; // to[i] 表示第 i 条边指向的点 int nxt[MAXM]; // nxt[i] 表示和第 i 条边同一起点的上一条边的下标 int val[MAXM]; // val[i] 表示第 i 条边的权值不带权图可以不要 int tot; // 当前边总数同时充当“边下标计数器”这里的核心思路是head[u]不是直接存邻接点而是存“边”的编号。拿到边编号 i 之后to[i]才是真正的邻接点nxt[i]则是同一起点 u 在插入这条边之前的那条边的编号。用大白话说head 就是每个点维护的一条“边链表”的表头nxt 把属于同一个点的所有边串起来需要一个额外的维度用来做 DP 或查权值。为什么要用“头插法”而不是“尾插法”因为头插法快。每次加一条边我只需要把新边的 next 指向原来的 head[u]再更新 head[u] 为新边下标全程 O(1)不需要额外记录每条链的尾部。2.2 加边函数一个经典的几行代码大部分情况下加边函数长这样void add_edge(int u, int v, int w) { to[tot] v; // 第 tot 条边指向 v val[tot] w; // 权值 nxt[tot] head[u]; // 新边的“上一条同起点边”就是之前的 head[u] head[u] tot; // 更新表头 } // 无向图就调两次 // add_edge(u, v, w); add_edge(v, u, w);有的教程会把tot初始化为 0用head初始化为 0 表示空也有的把head初始化为 -1tot初始化为 0遍历终止条件是i ! -1。两种写法都能用但我个人更推荐head置 0、tot从 0 开始、循环用i判断真假的写法省得 memset 成 -1也能少写几个比较运算符。不过这里没有绝对只要你团队或自己习惯统一就行最怕的是写两套混着用改 bug 改到怀疑人生。遍历点 u 的所有邻接点标准写法是这样的for (int i head[u]; i; i nxt[i]) { int v to[i]; int w val[i]; // do something }这个循环从 head[u] 开始每访问一条边就通过 nxt 跳到同起点的“上一条边”直到 i 变成 0。注意这个顺序是逆序的最后插入的边最先被访问到。大多数算法并不关心邻接点的遍历顺序所以问题不大但如果你要从 1 到 n 按序号处理边、或者需要在遍历中动态加边的场景就要格外注意这个特性。2.3 为什么无向图要把容量设为两倍无数新手第一次写边表法数组开成MAXM MAXN跑无向图直接越界崩溃调试半天还看不见问题。因为无向图里每条边要存两次比如add_edge(u,v)和add_edge(v,u)所以边数组大小至少要开成2 * MAXM。这里说的MAXM通常指“单方向边数的最大值”也就是题目给的最大有向边数遇到无向图直接乘 2。我的习惯是不管有向无向一律开2 * MAXM 5多留 5 的余量。因为有些题目加边次数甚至比 M 还多比如网络流里的拆点、辅助边提前留余量能避免很多难以排查的越界问题。至于为什么是 5 而不是 1纯粹是强迫症给缓冲区留点余地别问问就是以前被越界坑过。3. 完整入门实操用边表法存一棵无向树并统计子树大小3.1 建图环节一个可以直接抄的模板我们拿一个最常见的场景练手给一棵 n 个节点的无向树n 在 1e5 级别要求统计每个节点的子树大小。这类题用边表法写非常典型。先完整地把代码骨架贴出来#include bits/stdc.h using namespace std; const int MAXN 100005; const int MAXM 200005; // 无向树每条边存两次 int head[MAXN], to[MAXM], nxt[MAXM], tot; int sz[MAXN]; void add_edge(int u, int v) { to[tot] v; nxt[tot] head[u]; head[u] tot; } void dfs(int u, int fa) { sz[u] 1; for (int i head[u]; i; i nxt[i]) { int v to[i]; if (v fa) continue; // 无向图要避免走回父节点 dfs(v, u); sz[u] sz[v]; } } int main() { int n; cin n; for (int i 1; i n; i) { int u, v; cin u v; add_edge(u, v); add_edge(v, u); } dfs(1, 0); for (int i 1; i n; i) { cout i : sz[i] \n; } return 0; }这个代码看起来很简单但里面有两个细节值得展开说说。第一个细节为什么无向图 DFS 要传父节点。因为无向边等于双向可达如果 DFS 不记录父节点从 u 走到 v 之后v 遍历邻接点时又会走回 u形成死递归。所以if (v fa) continue是必须的。这个 fa 参数本质上是在遍历树上扮演“禁止回头”的作用特别是树没有环时只需要记住父节点就可以保证不重复访问。第二个细节子树大小统计的时机。sz[u] 1表示自己本身也算一个节点然后循环里每递归完一个儿子就把儿子的 sz 累加到自己的 sz 上。这段逻辑其实就是后序遍历先递归到底再一层层往上累加。边表法在这里没有额外干扰就按照深度优先依次访问每个邻接点顺序无所谓只要不重不漏就行。3.2 升级版求树的重心见识边表配合 DFS 的威力学会了子树大小再往上走一步就是“求树的重心”删掉某个节点后剩余最大连通块的大小最小。这个节点就是重心。用边表法实现最舒服的地方在于你在 DFS 过程中可以同时拿到每个节点的“儿子们的大小”和“父方向那颗子树的大小”两个量一拼就是一个节点被删掉后的最大连通块大小。int ans 1e9, ans_node -1; void dfs2(int u, int fa, int n) { sz[u] 1; int max_part 0; for (int i head[u]; i; i nxt[i]) { int v to[i]; if (v fa) continue; dfs2(v, u, n); sz[u] sz[v]; max_part max(max_part, sz[v]); } // 父方向那一块的大小是 n - sz[u] max_part max(max_part, n - sz[u]); if (max_part ans) { ans max_part; ans_node u; } }这里如果换成 vector 存图也完全能写但边表法写起来更“一气呵成”你不用关心 vector 遍历的时候迭代器怎么处理也不用担心 DFS 递归和容器内部扩容产生冲突就是老老实实通过 head 走到边表末尾。对于树这种递归密集型问题边表法的遍历稳定性给人心理上的安全感这种感觉写多了就会懂。3.3 带权图把 val 数组用起来刚才的树是无权树如果题目给的是带权图比如边权代表长度、花费、容量加边函数只要稍微扩展一下就行。void add_edge(int u, int v, int w) { to[tot] v; val[tot] w; nxt[tot] head[u]; head[u] tot; }带权边存好之后后面跑 DFS、Dijkstra、SPFA、DFS 找增广路都能在循环里拿到int w val[i]直接用。有一说一像这种用下标关联多个数组的方式有人可能觉得不如struct Edge { int v, next, w; }清晰但老手还是普遍推荐裸数组原因是竞赛里 memset 和 memcpy 对连续裸数组更友好而且结构体数组在 Cache 层面不一定比几个并列数组好到哪去。个人喜好第一但裸数组绝对不会让你吃亏。4. 边表法的进阶用法和周边扩展4.1 成对反向边与 i^1 技巧网络流必备边表法有一个震惊新手的经典操作把一条边和它的反向边连续存放用异或 1 瞬间找到对方。做法是先tot1或cnt1然后正向边占下标 1反向边占下标 2正向边占下标 3反向边占下标 4以此类推。这样任何一条边的编号 ii^1都能得到它的反向边编号。void add_flow_edge(int u, int v, int cap) { to[tot] v; cap_val[tot] cap; nxt[tot] head[u]; head[u] tot; to[tot] u; cap_val[tot] 0; // 反向边初始容量为 0 nxt[tot] head[v]; head[v] tot; } // 使用时正向边下标是 i反向边下标是 i^1为什么必须是相邻下标因为唯一性依赖1^10? 不对注意如果tot从 1 开始1 的反边是 0但这不行因为数组下标 0 通常作“空指针”。所以更标准的做法是从tot 1开始连续插入两条边编号 1 和 2 是一对3 和 4 是一对。数字 1 的二进制是 01异或 1 得到 00不对我们这里编号从 1 开始的话1^10就不满足相邻了。实际上竞赛里常用的标准是让边编号从2开始即第一个正向边编号为 2反向边编号为 32^133^12这样永远避开 0 下标。所以代码里应该tot 1之后先tot变成 2或者干脆tot 2开始再加边。这里面细节多我后面常见问题章节再展开。这个技巧在最大流算法Dinic、ISAP里几乎是标配因为每一次增广都要同时修改正向边剩余容量和反向边剩余容量如果边表不支持快速找到反向边你得遍历邻接表去搜复杂度直接没法看。写网络流题的时候这一步能不能写好直接决定你能不能 AC。4.2 扩展结构体把边信息封装起来如果你实在觉得“4 个数组并排”太裸可以封装成一个结构体struct Edge { int to, nxt, w, flow, cost; } edge[MAXM]; void add_edge(int u, int v, int w) { edge[tot] {v, head[u], w, 0, 0}; head[u] tot; }这种写法在可读性上有明显提升尤其是边需要同时记录流量、费用、容量、编号等多个属性时一个结构体全装下代码不容易乱。而且从访问速度角度看一次内存读入整个 Edge 结构体Cache 利用率在多数情况下也不差。我的经验是如果边属性 3 个以下裸数组真够用如果边属性超过 4 个比如费用流里要维护cost、cap、flow、to、next那还是结构体香不然你会被多个数组的下标对应关系折磨到崩溃。结构体版本加边时要用到大括号初始化注意和数组版本的to[tot] v区分开。实际项目里我一般会用结构体版本写网络流用裸数组版本写树论题因为树论题边属性少拆开写能少敲几个字母。4.3 边表法在 Dijkstra 堆优化中的实战表现树论之外边表法最常见的应用就是跑最短路。堆优化 Dijkstra 里每次从优先队列取出一个距离最小的节点然后遍历它的所有出边更新邻接点的距离。这段逻辑放到边表法上简直是完美契合void dijkstra(int s) { memset(dist, 0x3f, sizeof(dist)); dist[s] 0; priority_queuepairint,int, vectorpairint,int, greaterpairint,int pq; pq.push({0, s}); while (!pq.empty()) { auto [d, u] pq.top(); pq.pop(); if (d ! dist[u]) continue; for (int i head[u]; i; i nxt[i]) { int v to[i]; int w val[i]; if (dist[v] dist[u] w) { dist[v] dist[u] w; pq.push({dist[v], v}); } } } }这里你看到的就是边表法最舒服的用法往循环里一钻to[i]给邻接点val[i]给边权根本没有多余的东西。如果你用 vector 存 pair写法也不难但每次遍历都要通过 vector 迭代器取 pair 的 first/second实际跑起来还是比连续数组略慢一丢丢。竞赛里卡常的话这“一丢丢”可能就从 TLE 变成 AC。4.4 和 vector 邻接表共存什么时候别硬换边表法并不是银弹。如果你的图需要反复在程序里“添加、删除、修改边”而且删除不是标记一下就算是真正要把边从链表里摘除那边表法反而麻烦。因为数组模拟的链表删除一条边需要维护前驱关系或者引入del标记数组代码量蹭蹭往上涨。这种场景动态数据的std::list或者手写双向链表更适合但竞赛里其实很少需要动态删边所以边表法统治了大多数 OI 和算法题场景。我自己写代码的习惯是图的规模小且不会递归很深直接用 vector图的规模大、递归深、或者要跑网络流无脑选边表法。这里面没有高下之分关键是知道每种方案的计算模型是什么。5. 新人最容易踩的四个坑与调试心得5.1 无向图数组开小越界越到怀疑人生刚才已经强调过无向图要开双倍边数组。但实际操作中有些题不是明显的无向图而是“双向边”藏在描述里比如“道路可以双向通行”或者“节点之间互相可达”。如果你只按有向图大小开数组跑出来可能是偶发崩溃因为访问越界并不一定马上触发段错误可能只是悄悄覆盖了别的数组导致结果错误、行为诡异。我的排查经验是每个样例都过一交上去就挖坟考虑数组大小先检查MAXM是否开到了2 * 最大边数 5。这个检查 10 秒就完成却能省下半小时的 gdb 时间。5.2 head 初始化和循环终止条件混用这是另一个超大坑。如果你用memset(head, -1, sizeof(head))初始化遍历循环就该写成for (int i head[u]; i ! -1; i nxt[i])并且nxt[tot] head[u]继续把 -1 串起来。如果你用head初始化为 0循环就是for (int i head[u]; i; i nxt[i])。两者都行最怕的是初始化用 -1循环却写成了i这样i-1时跳出循环实际上第一遍循环体压根不会执行所有点都遍历不到结果自然全是 0。这类 bug 特征很典型程序不崩溃但输出明显不对。我建议直接把两种方案写进自己的模板里不要每次现想。模板固定一套以后写题直接复制省得手滑。5.3 网络流反向边的 tot 初始值搞错反向边i^1的技巧有个前置条件正向边和反向边必须成对连续存放而且数组下标要从一个偶数起始值开始。最安全的方式是把tot初始化为 1然后每次加边时先tot得到 2再加正向边再tot得到 3加反向边。这样正向边编号是偶数反向边是奇数i^1一定成对。如果tot从 0 开始0 和 1 理论上是一对但 0 又要当作空指针遍历时for (int i head[u]; i; ...)在遇到反向边 0 时会直接停循环导致整个链遍历不全。这是一个极其隐蔽的 bug报错方式也是“答案为 0 或死循环”非常折磨人。我当年第一次写 Dinic 的时候被这里卡了两个小时从那以后我遇到网络流就老老实实int tot 1;。5.4 调试技巧打印边表结构一眼看出问题边表法不好调试因为它是“链式”结构不像 vector 数组那么扁平直观。我常用的办法是在关键位置打印每一条边的完整结构void debug_graph(int n) { for (int u 1; u n; u) { cerr u u : ; for (int i head[u]; i; i nxt[i]) { cerr ( i - to[i] ) ; } cerr \n; } }这种打印能很清楚地看到每个点的邻接链是怎么串起来的。如果发现某个点的链特别短或者某条边的 to 值明显越界那八成是数组开小了、加边传参传反了、或者 head 初始化错了。做算法题多花 30 秒打印 debug 信息往往比瞪眼观察代码好使。5.5 边下标越界导致的内存覆盖怎么快速定位还有一种特别难缠的情况to[tot] v时 tot 越界写到了其他数组的内存里去表面运行没事但实际上某个变量被悄悄改了最后答案错得离谱。这种 bug 单纯靠 gdb 断点可能很难抓。我的办法是开一个编译选项或者加一个断言assert(tot MAXM - 1);每次加边后检查一下边界一旦越界程序立刻崩给你看这比“跑完才发现不对”要高效得多。实际做题时如果怀疑数组越界就在add_edge里临时加这一行用 assert 暴力把你带到违规现场定位到具体是哪一步越界然后针对性处理。最后分享几点我自己的经验图论题写多了你会发现代码本身往往不是最难的部分难的是数据结构跟算法之间的匹配。边表法这套东西第一次接触确实有点绕但一旦你写顺了它基本可以变成你图论代码的“默认底座”。至少在数据量大、递归深、要反复增删反向边的场景边表法是我最信任的选择。另外一个小建议平时准备一个自己的模板把add_edge、dfs、debug_graph这些常规函数固定下来用场上的时候直接调用别在比赛里临场回忆“到底是 head[u] 还是 edge[i].head”。很多时候稳定发挥就赢在不犯低级错误上。真心希望这篇文章能让你少踩几个我当初踩过的坑早日把边表法用得跟喝水一样自然。