1. 边表法到底是什么：从一次MLE说起
两年前我第一次在比赛里写图论题，邻接矩阵一开就是int g[5005][5005]，数据范围看着不大，结果一提交直接Memory Limit Exceeded。那次之后我才认真去研究边表法，才发现这么个朴素的存图方式，居然能把我从内存崩溃的边缘拉回来。
边表法，全称是链式前向星（也叫静态邻接表），是一种用数组来模拟链表、按“边”为单位存储图结构的方法。它跟我们熟悉的邻接矩阵不同，不是开一个 N×N 的二维数组去记录“点与点之间是否有边”，而是把每一条边独立存下来，再用类似“头插法”的方式挂在起点上。核心思想就一句话：我只存实际存在的边，不为不存在的边浪费内存。
这个东西特别适合两类场景：一是图很大但边很少的稀疏图，比如 N=10万、M=20万这种，邻接矩阵直接开不了，但边表法一点压力没有；二是算法竞赛里需要频繁遍历某个点的所有邻居的场景，因为边表法天生就是为“顺着起点找边”设计的。哪怕你只是学数据结构、做工程优化，只要碰过图论相关的需求，边表法都值得掌握。
这篇文章我想把这套东西彻底讲透，不光是给你贴一份可以运行的代码，而是把它背后的设计逻辑、每个数组到底是干什么的、为什么这样写效率最高、以及我这些年踩过的坑全部摊开来说。保证你读完能自己手写一个边表法，并且知道在什么场景下该用它、什么场景下该换别的方案。
2. 三种存图方式对比：为什么偏偏是边表法
2.1 邻接矩阵的致命软肋
先聊聊大家最容易上手的邻接矩阵。它的思路特别直观：开一个vector<vector<int>> g(n, vector<int>(n))，g[i][j]直接表示 i 到 j 有没有边。判断两点是否连通是 O(1) 的，写起来也最简单。
但问题在于空间。一个 N 个点的图，不管边有多少条，邻接矩阵固定要占 N² 个格子。如果 N 是 5000，那就是 2500 万个 int，大概 100MB，在很多在线评测系统里已经接近极限。如果 N 是 10 万，N² 直接是 10 的 10 次方，想都不用想。就算你改用vector<bool>（每个元素只占 1 比特），也得 12.5GB，完全不是常规内存能扛的。
还有一个隐藏问题：遍历某个点的所有出边，邻接矩阵的做法是循环 n 次，挨个检查g[u][i]是不是有值。如果这个点的出边很少，大部分时间都浪费在无效检查上。稀疏图里这是很奢侈的行为。
2.2 动态邻接表的代价与问题
既然邻接矩阵浪费空间，那自然地就会想到用vector<int> 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而不是定长数组：
vector<int> 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 当作邻居走回来，形成无限递归。
广度优先遍历（BFS）
BFS 在边表中的写法也很经典：
queue<int> 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_queue<pair<int, int>, vector<pair<int, 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((N+M)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 { vector<int> 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当邻接表效率又太差，最后绕了一圈，还是回到边表法的思路，用几个稀疏数组把所有关系存起来，速度快、内存稳、还能直接落盘。那一刻我真正体会到，数据结构的本质不是炫技，而是对问题规模与访问模式的深刻理解。
