1. 边表法到底是什么从一次MLE说起两年前我第一次在比赛里写图论题邻接矩阵一开就是int g[5005][5005]数据范围看着不大结果一提交直接Memory Limit Exceeded。那次之后我才认真去研究边表法才发现这么个朴素的存图方式居然能把我从内存崩溃的边缘拉回来。边表法全称是链式前向星也叫静态邻接表是一种用数组来模拟链表、按“边”为单位存储图结构的方法。它跟我们熟悉的邻接矩阵不同不是开一个 N×N 的二维数组去记录“点与点之间是否有边”而是把每一条边独立存下来再用类似“头插法”的方式挂在起点上。核心思想就一句话我只存实际存在的边不为不存在的边浪费内存。这个东西特别适合两类场景一是图很大但边很少的稀疏图比如 N10万、M20万这种邻接矩阵直接开不了但边表法一点压力没有二是算法竞赛里需要频繁遍历某个点的所有邻居的场景因为边表法天生就是为“顺着起点找边”设计的。哪怕你只是学数据结构、做工程优化只要碰过图论相关的需求边表法都值得掌握。这篇文章我想把这套东西彻底讲透不光是给你贴一份可以运行的代码而是把它背后的设计逻辑、每个数组到底是干什么的、为什么这样写效率最高、以及我这些年踩过的坑全部摊开来说。保证你读完能自己手写一个边表法并且知道在什么场景下该用它、什么场景下该换别的方案。2. 三种存图方式对比为什么偏偏是边表法2.1 邻接矩阵的致命软肋先聊聊大家最容易上手的邻接矩阵。它的思路特别直观开一个vectorvectorint g(n, vectorint(n))g[i][j]直接表示 i 到 j 有没有边。判断两点是否连通是 O(1) 的写起来也最简单。但问题在于空间。一个 N 个点的图不管边有多少条邻接矩阵固定要占 N² 个格子。如果 N 是 5000那就是 2500 万个 int大概 100MB在很多在线评测系统里已经接近极限。如果 N 是 10 万N² 直接是 10 的 10 次方想都不用想。就算你改用vectorbool每个元素只占 1 比特也得 12.5GB完全不是常规内存能扛的。还有一个隐藏问题遍历某个点的所有出边邻接矩阵的做法是循环 n 次挨个检查g[u][i]是不是有值。如果这个点的出边很少大部分时间都浪费在无效检查上。稀疏图里这是很奢侈的行为。2.2 动态邻接表的代价与问题既然邻接矩阵浪费空间那自然地就会想到用vectorint g[N]这种动态数组来存每个点的邻居列表。这也叫邻接表C 里用 STL 实现起来很方便g[u].push_back(v)就完事。邻接表在空间上是按实际边数增长的平均下来很省。但它有几个让我不太舒服的地方第一每次push_back都可能触发内存重新分配vector 扩容的时候要把旧数据拷贝到新地址频繁插入时性能有明显抖动。在很多在线评测的极限数据下这种抖动可能就会让你超时。第二每一条边是一个int存在 vector 内部还是连续内存但不同点的 vector 分布在堆的不同位置遍历时 CPU 缓存命中率不如纯数组。不要小看这个差异在大规模图遍历时缓存局部性直接决定程序快慢。第三如果你想在遍历过程中删除某条边或者说要维护反向边、快速找到边的编号做某些操作vector 的动态结构并不好处理。2.3 边表法的设计哲学用数组模拟一切边表法的做法是把所有边一股脑放进几个结构相同的数组里用数组下标充当“指针”来串联关系。它本质上是在手动实现一个“内存池 头插法链表”但比手写链表节点更简洁因为不涉及动态分配所有边在插入前就已经能预估总条数直接开好数组。为什么这种“退回到 C 语言时代”的做法反而更优秀核心原因是两个字可控。用数组意味着内存是连续预分配的没有堆分配的碎片问题也没有new/delete的开销。用下标代替指针意味着我们保存的不是地址而是整数编号这种做法既可以被 C 高效处理也可以直接序列化到文件里甚至可以拿来做一些“按边编号”的高级图算法比如网络流里的反向边索引或者 Tarjan 求桥时判断父子边。我见过很多初学者觉得边表法晦涩觉得“我明明可以用 vector干嘛自找麻烦”。我的理解是vector 是工具边表法是数据结构思维。当你在做高性能计算、参加算法竞赛、或者面对几十万甚至上百万条边的工程问题时边表法这种极度贴近底层的存储方式就是最可靠的方案之一。3. 核心细节解析四个数组与链式前向星的构建3.1 数组到底存了什么边表法的标准实现需要四个数组或者说三个必需 一个可选。我用一个具体例子来讲。假设你要存这样一张有向图5个点4条边 1 - 2 1 - 3 2 - 4 3 - 5用边表法核心变量是const int N 100005; // 点的最大数量 const int M 200005; // 边的最大数量有向图一般开两倍 int head[N]; // head[u] 表示从 u 出发的第一条边在数组中的编号 int to[M]; // to[e] 表示编号为 e 的边指向的终点 int nxt[M]; // nxt[e] 表示编号为 e 的边的下一条兄弟边的编号 int w[M]; // w[e] 表示编号为 e 的边的权值无边权时不需要 int cnt 0; // 当前已经使用的边的总数这里的命名我用的是nxt很多人也写成next不过next在 C 标准库中有歧义风险建议用nxt或者ne。逐个解释head[u]这是“入口”相当于链表头指针。它存的是一个整数这个整数指向to数组中的某个位置而这个位置上的边就是 u 的第一条出边。如果head[u] -1说明 u 没有出边。to[e]这条边的终点是谁。比如我们插入一条边u - v那么to[e] v。nxt[e]存的是“以同一个点为起点上一条插入的边的编号”。所有从这点出发的边通过nxt像拉链一样串成一条链链的末尾那条边的nxt是 -1。w[e]存权值。不想写模板的话可以在存储时直接开但如果是无向图、且需要同时存储正向边和反向边就要考虑成对插入的技巧后面专门讲。3.2 加边函数的每一步推导加边的代码通常长这样void add(int u, int v, int weight) { to[cnt] v; w[cnt] weight; nxt[cnt] head[u]; head[u] cnt; cnt; }第一次接触的同学大概率一脸懵为什么nxt[cnt]要等于head[u]为什么head[u]要更新为cnt顺序能换吗我用生活化的比喻拆解一下。想象每个点是一个公告栏head[u]指向的是“最新贴上去的那张便利贴”。每次新来一张便利贴新边你不是把它放到公告栏的最后面而是直接贴在公告栏最前面然后把原来的第一张往后挤一位。新的便利贴的“下一条”就指向原来那张原来那张的位置记录在head[u]里。所以顺序绝对不能乱先把终点和权值存进to[cnt]、w[cnt]此时这条边自身内容已经完整了。让新边的nxt[cnt] head[u]也就是新边指向旧的第一条边完成拉链。再更新head[u] cnt让公告栏最上面变成新边。最后cnt为下一条边腾出位置。如果你先更新head[u]再存nxt[cnt]那nxt[cnt]拿到的就是新边自己链表直接断掉、形成环遍历时会死循环。这是我当年踩过的第一个低级Bug。3.3 无向图的成对存储技巧如果是无向图每次输入u v实际上要加两条方向相反的边u - v和v - u。这两条边在存储上有一个非常巧妙的性质如果初始cnt 0那么先加的边编号是偶数后加的对应反向边编号是奇数或者说它们是相邻的编号 ^ 1就能得到另一条。这也是为什么很多代码里写add(u, v); add(v, u);要连续。因为对于“无向图里需要从一条边快速找到它的反向边”的场景——比如网络流的增广路径回退——e ^ 1就搞定了性能极高。这是个很小的细节但理解了它你写网络流模板的时候会舒服很多。如果你用vector实现邻接表要从一条边找反向边你还得在结构体里额外存一个rev下标或者用 map 映射两头都不讨好。这就是我说的“边表法更可控”的典型体现。3.4 初始化与边界一切从 -1 开始因为head数组存的是“边的编号”而一条边都没有时编号自然可以约定为-1。所以初始化时要把head全部清成-1。我还见过有人用 0 作为空标志这也可以但那样的话边的编号就要从 1 开始加边前cnt 1否则会跟“第一条边编号 0”冲突。从 0 开始还是从 1 开始本身没有绝对的对错但你必须保持一致。我最开始混用过这两种约定结果遍历时少遍历了一条边调试了一下午。后来我的习惯是cnt 0、head初始化为-1。这样for循环遍历边的时候条件写for (int e head[u]; e ! -1; e nxt[e])非常顺手。memset(head, -1, sizeof(head)); // 在全局数组时可以直接这样清 cnt 0;如果你开的是vector而不是定长数组vectorint head(N, -1);原理完全一样只是动态扩容稍微灵活一点。4. 实操过程与核心环节实现从DFS到最短路的完整落地4.1 存完图之后怎么遍历核心循环的三种写法深度优先遍历DFS边表法配合 DFS 是很多树/图算法的基础例如求连通块、拓扑排序、树上DP。模板如下void dfs(int u, int fa) { for (int e head[u]; e ! -1; e nxt[e]) { int v to[e]; if (v fa) continue; // 无向图去重防止走回头路 dfs(v, u); } }这里最需要注意的是“父节点”的判断。存无向图时你加了一条u - v就必然有一条v - u的反向边。DFS 从 u 走到 v 时如果不去判断v fa那么dfs(v, u)又会把 u 当作邻居走回来形成无限递归。广度优先遍历BFSBFS 在边表中的写法也很经典queueint q; bool vis[N]; q.push(s); vis[s] true; while (!q.empty()) { int u q.front(); q.pop(); for (int e head[u]; e ! -1; e nxt[e]) { int v to[e]; if (!vis[v]) { vis[v] true; q.push(v); } } }BFS 本身跟图的存储方式关系不大关键在于“遍历某个点所有邻居”这个动作。边表法保证了你遍历 u 出边的次数正好等于 u 的出度不浪费任何一次检查。Dijkstra 最短路最短路实现里边表法的优势尤为明显。如果你用邻接矩阵松弛操作要写if (dis[v] dis[u] g[u][v])前提是矩阵够大但如果是 10 万点、20 万边的大图根本开不了矩阵。边表加堆优化 Dijkstra 是标准解法之一void dijkstra(int s) { memset(dis, 0x3f, sizeof(dis)); memset(done, 0, sizeof(done)); dis[s] 0; priority_queuepairint, int, vectorpairint, 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 (int e head[u]; e ! -1; e nxt[e]) { int v to[e]; if (dis[v] d w[e]) { dis[v] d w[e]; pq.push({dis[v], v}); } } } }你只需要从head[u]出发沿着nxt链走一遍就得到了 u 的所有出边。每次松弛拿w[e]不需要额外查表。时间复杂度 O((NM)logN)在稀疏图里几乎逼近理论最优。4.2 完整示例用边表法建图并输出每条边的邻居为了避免空谈我拼接一个可以直接运行的完整例子。这个例子读入 n 个点和 m 条边建立有向图然后输出每个点的所有邻居。你可以在自己的编译器上跑一下把每一步对应起来看。#include bits/stdc.h using namespace std; const int N 100005; const int M 200005; int head[N], to[M], nxt[M], w[M], cnt; void add(int u, int v, int weight) { to[cnt] v; w[cnt] weight; nxt[cnt] head[u]; head[u] cnt; cnt; } int main() { int n, m; cin n m; memset(head, -1, sizeof(head)); cnt 0; for (int i 0; i m; i) { int u, v, weight; cin u v weight; add(u, v, weight); // 如果是无向图再加 add(v, u, weight); } for (int u 1; u n; u) { cout 点 u 的邻居: ; for (int e head[u]; e ! -1; e nxt[e]) { cout to[e] (边号 e ) ; } cout endl; } return 0; }注意看输出时“邻居的顺序”因为是头插法所以遍历出来的邻居顺序和输入顺序是相反的。如果你需要保持原输入顺序要么输入时从末尾插入但那样找尾部需要额外数组要么最后对每个点的边编号排序。我目前做过的大部分算法题都不依赖这个顺序所以头插法完全够用。如果你用的是 C 的bits/stdc.h在工程环境可能不是标准头文件但在算法竞赛和刷题平台基本没问题。工程环境建议拆成iostream、cstring、queue等具体头文件。4.3 参数计算开数组的容量到底怎么定开数组大小是有讲究的开小了会越界开大了浪费。最安全的公式是这样如果是有向图边的最大数量就是输入限制的 m 上限数组开到2 * m_max 5就足够。如果是无向图每条边会存两次边的最大数量是2 * m_max所以数组也要开成2 * m_max 5。如果你还要加反向边比如网络流那次数可能更多按实际需求乘倍数。我做题时的习惯是看题目数据范围如果n 1e5, m 2e5我直接开const int N 100005; const int M 400005;。为什么要多开一倍因为我怕无向图加双倍边万一题目有“多条重边”也要存下来那M不够就直接越界报错。多开一点空间换来的是心安内存一般不会超。4.4 边表法实现时的关键代码习惯在真实比赛里我总结了一套自己的编码“肌肉记忆”第一全局数组自动零初始化。但head需要手动初始化为 -1。我一般直接在main最前面写memset(head, -1, sizeof(head));不要偷懒省略。第二add函数里四条赋值语句的顺序。我用注释把每一步标注清楚防止手滑写反。写多了之后这都不算事但刚开始一定养成交叉检查的习惯。第三遍历时刻别把head[u]写成head[v]。这种问题在变量名短时很难发现但效果是灾难性的——你可能遍了个寂寞程序却不会报错。第四如果你把代码封装进结构体或者类里那么cnt不能每次建图都忘了重置。我在多组测试数据的题目里曾经因为忘记cnt 0导致新图把旧图的边也遍历了出来答案错得离谱。5. 常见问题与排查技巧实录那些年我踩过的坑5.1 遍历时出现死循环或段错误现象for (int e head[u]; e ! -1; e nxt[e])里的e跳来跳去跳不出去或者跑到一个巨大地址导致段错误。排查思路检查head是否初始化为 -1。如果没有head[u]会是一堆随机值遍历从错误的边号开始。检查add函数顺序。先更新head再赋值nxt会让新边的next指向自己形成环。这种情况尤其隐蔽因为程序不会立刻崩它只是进入死循环。检查数组大小。如果边的数量超过了M写入to[cnt]时就越界了会污染相邻数组导致各种玄学问题。这种越界往往不会立刻触犯系统所以特别难找。我给自己的排查顺序是head 初始化 → add 顺序 → 数组容量。绝大多数边表法的Bug都能在这三步里找到。5.2 无向图遍历时重复访问现象DFS 递归栈溢出或者 BFS 队列里面出现一大堆重复节点。原因分析无向图加边时add(u, v)和add(v, u)都加了DFS 到 v 之后它的邻居列表里有 u不处理就会回头。上面提到加if (v fa) continue;是树/无环图的做法但如果图里有环仅靠v fa判断是不够的你必须配一个vis数组已经访问过的节点直接跳过。void dfs(int u) { vis[u] true; for (int e head[u]; e ! -1; e nxt[e]) { int v to[e]; if (vis[v]) continue; dfs(v); } }这里vis[v]的判断至关重要。无向图有环时一个点可能通过不同路径被多次访问不标记就死循环。5.3 重边与自环的处理图里可能出现两条完全一样的边u - v也可能出现自环u - u。边表法天然支持重边因为它是按“边”为单位的每条边独立存重复输入就是多存一条不会覆盖。自环也一样add(u, u)会把起点和终点都设为同一个遍历时to[e]等于u逻辑上没问题。但要注意如果算法题目要求“去重”你得在加边阶段自己处理比如用 set 或者排序去重边表法本身不帮你去重。在求最短路时重边通常不影响正确性松弛时自然取最小但如果求“边数”或“方案数”重边会导致结果翻倍需要特别注意。5.4 多组测试数据未清零竞赛题经常给 T 组数据每组都要新建一张图。如果你用的全局数组上一组数据残留的head、cnt没清干净会直接污染下一组。很多选手超时或答案错误的第一反应是算法不够快其实往往是没清零。我的习惯是在每组数据开头写memset(head, -1, sizeof(head)); cnt 0;如果题目的边数超过之前的容量我情愿把数组开大也不愿意在每组数据里重新用vector动态分配来省内存。5.5 边表法 vs 邻接表的纠结算力对比我一边写文章一边回忆那些年自己用两类存图方式写过的题目发现有几个公认的“最佳实践”当 n 很小比如 1000 以内且需要判断任意两点是否连通时邻接矩阵反而更好因为 O(1) 查询带来的便利超过一切。当 n 在 1e5 以上且只做一次建图、多次遍历时边表法最合适。当图是动态增边的但你对增边次数没法预估时vector 邻接表可能更省心因为不需要预设M。这些权衡在我深度使用之后已经变成了直觉。我印象最深的是有一次处理一个 50 万个点、120 万条边的稀疏图最短路问题用边表法加堆优化 Dijkstra跑了不到一秒如果用邻接矩阵这台机器连图都存不进去。数据规模就是赤裸裸的选择标准。6. 工程化扩展从算法题到真实项目的思维迁移6.1 边表法在序列化与持久化上的优势我一直觉得不要把边表法当成一个只能用于比赛存图的“工具人”。它的本质是用紧凑的整数数组存储一个稀疏图所有信息可预测、可序列化、可随机访问。这个特性在工程上很值钱。举个例子你要把一张图存入文件或者数据库边表法数组化结构天然就是一行一行的整数cnt、head、to、nxt、w。你甚至可以直接把它们直接写到二进制文件里加载时一次性读入不需要做对象反序列化、指针恢复这类繁琐操作。相比之下如果用指针实现的链表结构序列化时你得靠相对偏移来模拟指针版本一升级就崩。6.2 缓存友好性为什么数组比链表快现代 CPU 在读取内存时会一次性加载一块连续的缓存行cache line。当你用数组存边时遍历to[e]和nxt[e]是在访问两个连续地址段CPU 能非常高效地预取。但用链表存边时每个节点分散在堆的不同位置每次访问都有可能触发 cache miss性能损失可能在 3-5 倍以上。这一点在你处理千万级边的图时会体现得非常直接。我有一次在本地测试两种存图方式跑同一个遍历任务边表法只需要 0.2 秒链表版却需要 0.8 秒差距大到根本不是算法本身的问题纯粹是存储结构决定的。所以工程上追求性能的地方我基本默认优先考虑数组化结构。6.3 进阶边表法与其他算法的组合使用边表法不是孤立存在的它在 LCA、树链剖分、网络流、最短路等算法中都扮演了“地基”的角色。比如在 LCA 倍增算法里需要 DFS 预处理深度和祖先边表法遍历邻接关系就很自然地完成了在 Tarjan 求强连通分量/桥时需要每条边只访问一次边表法的“边编号”可以帮我们精确判断一条边是不是树边、返祖边代码写起来干净且不容易出错。如果你对图算法的学习路径有一个清晰认识你会发现边表法几乎是一个必过的门坎。它不是最高级的玩法但它是你理解“用索引表达结构”这种底层思维的最佳起点。6.4 一个踩坑多次后的封装模板为了避免每次写题都重复造轮子我后来封装了一个简单的结构体版边表struct EdgeTable { vectorint head, to, nxt, w; int cnt; EdgeTable(int n, int m) { head.assign(n 5, -1); to.resize(m * 2 5); nxt.resize(m * 2 5); w.resize(m * 2 5); cnt 0; } void add(int u, int v, int weight 0) { to[cnt] v; w[cnt] weight; nxt[cnt] head[u]; head[u] cnt; cnt; } void add2(int u, int v, int weight 0) { add(u, v, weight); add(v, u, weight); } };这里用vector替代了固定数组既保留了所有边表法优点又不用每次都对具体 N、M 费神。add2是专为无向图准备的两次调用保证正反边相邻e ^ 1技巧依旧适用。这个模板我在多个项目中沿用至今几乎没有出过问题。7. 写在最后一点实在的经验之谈如果只让我给你一条关于边表法的学习建议我会说不要背代码去理解索引的指向关系。head是你进入一张图的钥匙nxt是同一起点上的“兄弟链”to是边的终点。你只要能在纸上把三次加边操作后的索引图画出来边表法就不可能再难倒你。我自己第一次手写边表法时连错三次才发现是add里赋值顺序的问题。后来养成了一个习惯每次新写图论题先用边表法手写建图部分再动算法主体。这个习惯让我的编码速度和对数据的掌控感都提升了不少尤其碰到需要“按边编号”做文章的高级算法时之前积累的底层熟练度就全成了优势。最后再说个真实体感不要觉得边表法只在比赛里有用。我后来在做一个社交关系分析的小项目时几百万条好友关系用邻接矩阵直接内存爆炸用unordered_map当邻接表效率又太差最后绕了一圈还是回到边表法的思路用几个稀疏数组把所有关系存起来速度快、内存稳、还能直接落盘。那一刻我真正体会到数据结构的本质不是炫技而是对问题规模与访问模式的深刻理解。