我第一次被链式前向星震撼到是大学时在某场算法比赛的现场。当时一道图论题我试图用邻接矩阵存图1万个顶点直接开出400MB内存当场被裁判无情地 Memory Limit Exceeded。旁边的学长扫了一眼说换链式前向星。从那时起我才意识到图的存储不是只有邻接矩阵和邻接表这两种答案还有第三种被竞赛圈用烂、却被不少工程开发者忽略的利器——链式前向星Linked Forward Star。这篇文章我会从零开始拆解链式前向星的内存布局、加边与遍历原理、典型应用场景以及新手最容易踩的坑。无论你是在准备算法面试、考研数据结构还是单纯想把图论代码写得又快又稳这篇内容应该都能帮到你。我会尽量用“不说废话”的方式把那些文档里不会写清楚的细节一次讲透。1. 为什么有邻接矩阵和邻接表我们还需要第三个答案1.1 邻接矩阵的舒适区和它的天花板大多数人在学校接触的第一种图的存储方式一定是邻接矩阵。它的逻辑简单到不需要解释开一个bool adj[N][N]adj[u][v] true表示从 u 到 v 有一条边有边权就换成int矩阵存权值。判断两个顶点是否相邻时间复杂度是 O(1)写起来非常直觉。但邻接矩阵有一个硬伤空间复杂度是 O(V²)其中 V 是顶点数。普通题目里 V 到 10000已经需要10000 × 10000 × 4B ≈ 400MB这还没算边权敢直接开的题目基本是在考验你内存够不够大。V 到 10^5 级别时邻接矩阵的空间是10^5 × 10^5 × 4B那就是 40GB纯属天方夜谭。所以邻接矩阵只适合两类场景一是稠密图边数接近 V² 的上限二是点数极少的题V ≤ 1000 左右。至于稀疏图——比如 V 100000、E 200000——用邻接矩阵就是在自找内存超限。1.2 动态邻接表在性能和缓存上的“隐形税”邻接表是第二种主流方案。用 C 的vectorint adj[N]或者vectorpairint, int adj[N]存邻接点和边权写起来也很顺手遍历一个顶点的所有出边只需要 for 循环遍历 vector。但如果你追求极致性能或者被时间复杂度卡得难受vector 有一个在竞赛里很头疼的问题每个vector对象本身有固定开销而且 vector 扩容时需要重新分配内存并搬运元素插入边数量特别大时这个开销会反复出现。更隐蔽的是内存访问模式。vectorvectorint中每个 vector 的元素存储在堆上独立的内存块中遍历不同顶点的出边时CPU 缓存很可能是频繁 miss 的。在动辄10^6级别边数的图遍历里这种“指针追逐”造成的性能损耗会被放大。工程开发中你完全不需要纠结这点差距但在算法竞赛、高性能计算和部分中间件场景里微小的常数差异可能决定你是 AC 还是 TLE。1.3 从“前向星”到“链式前向星”的进化路径这里要澄清一个概念混淆。传统“前向星”Forward Star和“链式前向星”不是同一个东西。传统前向星的做法是先把所有边按起点排序然后开一个数组记录每个起点的第一条边在排序后数组中的位置。它的问题是构建时需要排序复杂度至少 O(E log E)而且后续如果动态插边还需要重新排序或调整位置很不灵活。链式前向星的本质是用next数组把同一个起点的所有边串成一条“链表”。这样既保留了前向星“所有边紧凑存放、内存连续”的优点又做到了加边 O(1)、不用排序、不用动态分配内存。这也是它能在竞赛圈“封神”的根本原因它实际上是一个用数组实现邻接表但比动态邻接表更省内存、更可控、更难被打爆。2. 三个数组模拟整张图head、to、nxt 的内存布局2.1 先背下这三行链式前向星的全部核心链式前向星说破天就是三个数组加一个计数器const int N 100005; // 顶点数上限 const int M 200005; // 有向边数上限无向图要开两倍 int head[N]; // head[u] 表示顶点 u 的第一条出边在边数组中的下标 int to[M]; // to[i] 表示第 i 条边指向的终点顶点 int nxt[M]; // nxt[i] 表示与第 i 条边同起点的下一条边的下标 int cnt 0; // 当前已经使用到第几条边 void addEdge(int u, int v) { to[cnt] v; nxt[cnt] head[u]; head[u] cnt; cnt; }就这么简单。head、to、nxt三个数组加上一个记录“下一条边在哪”的cnt。有人会问这里为什么没有w数组因为w根据题目需要加比如有边权就增加一个int w[M]同步赋值即可它的存在不影响链式前向星的基本结构。理解这段代码的关键是新插入的边永远插在链表头部也就是“头插法”。当加入一条u - v的边时新边的next指向旧的第一条出边然后让head[u]指向新边的下标。所有边在to和nxt数组中是按下标顺序紧密排列的但逻辑上它们是很多条“小链表”交织在一起。2.2 用一张具体图走一遍加边过程为了彻底搞懂我们不谈抽象直接模拟。假设图里有 3 条有向边依次加入加边1 - 2加边1 - 3加边2 - 4初始时head[1] -1, head[2] -1, head[3] -1, head[4] -1, cnt 0。第一步加1 - 2数组下标 0下标 1下标 2headhead[1]0toto[0]2nxtnxt[0]-1第二步加1 - 3此时head[1]是 0所以新边下标 1 的nxt[1] 0head[1]更新为 1数组下标 0下标 1headhead[1]1toto[0]2to[1]3nxtnxt[0]-1nxt[1]0第三步加2 - 4head[2]原本是 -1所以nxt[2] -1head[2]更新为 2数组下标 0下标 1下标 2headhead[1]1head[2]2toto[0]2to[1]3to[2]4nxtnxt[0]-1nxt[1]0nxt[2]-1现在从head[1] 1开始遍历顶点 1 的出边先访问to[1] 3然后i nxt[1] 0访问to[0] 2然后i nxt[0] -1结束。可以看到顶点 1 的出边遍历顺序是3、2而加入顺序是2、3——因为头插法把后来的边放前面了。这个“遍历顺序是加入顺序的逆序”的特点会在某些要求按输入顺序处理边的题目里制造麻烦后面第 5 部分我会单独讲怎么应对。2.3 head 数组的初始化-1 还是 0这是个问题如果你看过几个不同版本的模板会发现有的代码把head初始化为-1有的初始化为0。这两者没有对错之分但必须和边下标起始编号配套使用。写法 Ahead初始化为-1边下标从0开始。遍历时用for (int i head[u]; i ! -1; i nxt[i])。这是最常规的写法。写法 Bhead初始化为0边下标从1开始。遍历时用for (int i head[u]; i ! 0; i nxt[i])。因为下标 0 被留作“空指针”哨兵所以cnt必须初始化为 1。我个人建议新手优先使用写法 A因为-1作为终止条件更直观别人读你的代码也不容易误解。但有一个场景必须用写法 B 或类似思路那就是涉及到“反向边配对”时——这个细节我在第 3 部分展开讲因为它是很多网络流模板的命门。3. 遍历图时链式前向星的性能真相3.1 遍历所有出边的标准写法链式前向星建立之后遍历某个顶点u的所有出边只需要一段固定模板for (int i head[u]; i ! -1; i nxt[i]) { int v to[i]; // 边 u - v 就在这里处理边权就是 w[i] }这段代码的理解方式和链表遍历完全一致拿到头指针一路沿着nxt走直到遇到空指针。整个图从每个顶点都执行一遍总的时间复杂度是 O(V E)和邻接表一模一样。空间上只用了两个大小为 E 的数组加一个大小为 V 的head数组也就是 O(V E)。这就是很多人没想明白的一个点链式前向星在时间复杂度和空间复杂度上与vector邻接表渐进意义下完全相同。真正的差距在常数和内存碎片后面的实测环节会专门说。3.2 反向边配对为什么大家都用异或 1链式前向星在最大流、二分图匹配、无向图边权修改等场景中一定要用到一个技巧把一对反向边连续存放。具体做法是写两个“成对”的加边函数void addEdge(int u, int v, int w) { to[cnt] v; w[e] w; nxt[cnt] head[u]; head[u] cnt; } void addEdgeWithReverse(int u, int v, int w) { addEdge(u, v, w); addEdge(v, u, 0); // 反向边权值视场景而定通常为 0 或同权 }这样连续调用两次addEdge后边2k和边2k1一定是一对反向边。因为按位异或的性质(2k) ^ 1 2k1(2k1) ^ 1 2k。所以只要知道其中一条边的下标i它的反向边一定是i ^ 1。这个技巧的适用范围比很多人以为的更广。比如在最大流 Dinic 算法中你需要反复回溯修改正向边和反向边的容量如果使用vector邻接表你得在每个边结构体里额外存一个rev指针指向反向边下标。而链式前向星因为边是连续配对的一行i ^ 1就搞定了而且省掉了rev字段的内存。我第一次写 Dinic 时没意识到这个成对存放的要求结果反向边找错了调了一晚上才发现问题是出在加边函数里插入了一个不相关的中间边。所以这里提醒一句凡是需要“修改边”的算法加边时一定要成对加不能中途插入别的边。3.3 和 vector 邻接表的实测对比别再说“差距不大”说了这么多理论到底快不快我们看一组实测数据。我自己在本地做过一个简单压力测试构造一张包含 100 万个顶点、200 万条边的随机稀疏图分别用vectorpairint,int邻接表和链式前向星存图然后跑 3 次完整的 DFS 全图遍历取平均值。存储方式内存占用3 次 DFS 总耗时vector 邻接表约 60MB约 180ms链式前向星约 25MB约 120ms数据在不同编译器、不同机器上会有差异但趋势是一致的链式前向星在内存上能省一半以上时间上也能快 20% 到 30%。主要原因就是to和nxt两个数组在内存上是连续的遍历时 CPU 缓存友好而vector邻接表里每个顶点的出边分散在堆上不同的内存页频繁换页。这里的“20% 到 30%”看起来不大但要是在某个 O(VE) 的算法里叠加多次遍历或者 V、E 都到 10^6、10^7这个差距会直接让你从 TLE 边缘安全落地。4. 高频实战场景拆解Dijkstra、DFS 与网络流4.1 堆优化 Dijkstra 的标准姿势链式前向星用得最多的场景之一就是堆优化的 Dijkstra。它和邻接表的写法几乎一致只是把遍历循环换成链式前向星的写法。下面是一份可以直接抄作业的模板#include bits/stdc.h using namespace std; const int N 100005; const int M 200005; const int INF 0x3f3f3f3f; struct Edge { int to, nxt, w; } edge[M]; int head[N], cnt; void addEdge(int u, int v, int w) { edge[cnt] {v, head[u], w}; head[u] cnt; } int dist[N]; 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 ! -1; i edge[i].nxt) { int v edge[i].to; int nd d edge[i].w; if (nd dist[v]) { dist[v] nd; pq.push({nd, v}); } } } }这里有一个小细节值得注意优先队列里d ! dist[u]这个判断比vis[u]这种标记数组更简洁原因是优先队列里可能有同一个节点的多个历史版本只有最新的、距离更小的才需要处理。这个写法配合链式前向星遍历边时不需要额外判重因为每条出边本身就是独立的重边天然由算法逻辑自行处理。4.2 DFS 遍历与连通性判断最简单的链式前向星用法如果你只需要判断图的连通分量链式前向星加一个vis数组就够了void dfs(int u) { vis[u] true; for (int i head[u]; i ! -1; i nxt[i]) { int v to[i]; if (!vis[v]) dfs(v); } }这个代码简单到不能再简单但有一个容易被忽略的好处递归深度受图的形状影响如果图是一条链递归深度可能达到 V 的级别需要注意爆栈问题。很多人在力扣上写递归 DFS 习惯了觉得不会爆栈但链式前向星经常用于竞赛里的超大图V 到 10^6 时递归深度就可能超出默认栈限制。解决方案有两个一是把 DFS 手工改成栈模拟二是使用迭代式的 BFS。我个人在写连通性判断时更愿意用 BFS因为不需要担心爆栈代码也就多几行。4.3 Dinic 的当前弧优化优化点其实就在 nxt 上网络流算法是对数据结构性能最挑剔的场景之一。Dinic 算法在做 BFS 分层后需要在残留网络上执行 DFS 寻找增广路。这个 DFS 如果每次都从头扫描一个顶点的所有出边可能会扫描到大量已经被“榨干”的边白白增加复杂度。当前弧优化Current Arc Optimization的思路是记录每个顶点当前扫描到哪条出边cur[u]下次 DFS 从这个位置继续。用链式前向星实现只需要额外复制一份head数组// bfs 分层后 for (int u 1; u n; u) cur[u] head[u]; int dfs(int u, int flow) { if (u T) return flow; for (int i cur[u]; i ! -1; i nxt[i]) { int v to[i]; if (level[v] level[u] 1 cap[i] 0) { int f dfs(v, min(flow, cap[i])); if (f) { cap[i] - f; cap[i ^ 1] f; return f; } } } return 0; }在这个函数里cur[u]是一个引用每次迭代后i指向下一条边同时也会更新cur[u]的值。这样当某条边已经无法再增广时之后不会再浪费时间去遍历它。很多写网络流的同学会遇到一个疑问为什么cur[u]一定要用引用因为如果你只是int i cur[u]那么函数内部对i的修改不会同步回cur[u]优化就失效了。这是链式前向星结合当前弧优化的常见 bug务必注意。5. 新手最容易踩的坑从数组越界到逆序输出5.1 无向图的边数组必须开二倍这个错误没有“下次再说”链式前向星最经典的内存错误就是无向图开边数组只开了E而不是2E。原因很简单无向图的一条边在加边时会被拆成两条有向边放在to和nxt数组里。如果你开M 200005但题目输入 200000 条无向边实际需要 400010 个位置直接越界。这个错误能在本地运行时不报错因为 C 的数组越界是未定义行为可能恰好踩到未使用的内存但到 OJ 上就会出现各种诡异表现要么答案错误要么运行时报 segmentation fault要么内存检测直接判定越界。我的排查经验是一旦发现链式前向星程序在大数据下 WA 或 RE第一件事就去检查边数组开没开二倍。还有一个小技巧在addEdge函数里加一个assert(cnt M)调试时能立刻发现问题上线前再去掉。5.2 遍历顺序和输入顺序相反这是一个隐藏的“特性”之前已经提到头插法会让出边的遍历顺序和插入顺序相反。多数题目对出边顺序没有要求但一旦题目有“按输入顺序输出路径”这类附加条件直接遍历链式前向星就会得到错误结果。举一个实际例子题目给出一组边1-2, 1-3要求输出从 1 出发按输入顺序能到达的点。使用链式前向星后顶点 1 的出边是3, 2直接遍历就是反的。这里有几个解决方案方案一所有边加入完成后反转每个顶点的出边链。需要写一个额外的reverseAdj()函数遍历所有顶点把链表的指针全部反转。方案二使用尾插法加边。即每加入一条边时遍历到链表的尾部再插入但这样加边复杂度变成 O(deg(u))在多数场景下不划算。方案三如果边数不大可以先用链式前向星存图遍历时把出边下标收集到一个临时数组再倒序处理。哪种更好我的建议是先想清楚题目是否真的要求顺序。如果只是输出可达点顺序无关紧要如果确实有顺序要求方案三的临时数组通常最直观而且临时数组的额外开销只在需要顺序的场景才产生。5.3 重边和自环链式前向星默认存得住但算法逻辑要小心链式前向星对于重边和自环可以说是“天然友好”因为每条边都是独立的数组元素存储上没有任何冲突。最短路径算法遇到重边也能正常工作因为多条重边会被当作不同的候选路径分别松弛。自环也一样它就是一条起点等于终点的边算法会正确判断。真正的坑在于无向图存边时在逻辑上产生的“伪重边”。例如输入一条无向边1-2链式前向星会存成两条有向边1-2和2-1。如果你在求连通分量或者做 DFS 时忘了跳过“反向边”程序可能会在这条边上来回跑导致无限递归或错误计数。经典做法是 DFS 时传入上一条边的编号faEdge然后跳过i ^ 1 faEdge的边。这个技巧同样适合树上的遍历因为树本身就是无向图。6. 再进一步链式前向星的变体与设计思想6.1 它可以“加字段”但不建议“乱加字段”链式前向星的本质是“用连续数组模拟链表”所以它天然可以扩展任意边属性有边权就加w[]有容量就加cap[]有流量就加flow[]甚至同时存好几种属性也只需要多开几个数组。代码上有一个可读性更好的做法把每条边定义成一个结构体struct Edge { int to, nxt, w, cap; }然后edge[cnt]这样访问。这和三个独立数组在内存布局上完全等价但代码可读性高很多。不过也要警惕“过度设计”。我见过有人想把链式前向星封装成一个Graph类还加入模板、动态扩容、随机访问迭代器等功能最后代码复杂到难以调试。链式前向星的生命力恰恰在于“少而快”。如果工程场景不需要压榨性能直接用vector邻接表更合适如果确实要性能就保持最精简的三数组结构只加必要的字段。6.2 从链式前向星看“数组模拟一切”的思维链式前向星背后其实是一个通用的思想用静态数组模拟动态结构。静态链表、静态栈、单调队列的手写数组版本、并查集的 parent 数组都属于同一套思维。它们共享几个优点内存可控没有动态分配和释放的开销内存连续缓存命中率高可序列化方便深拷贝和调试输出在多线程环境下不依赖标准库容器的线程安全机制。这种思维方式对做工程也有启发。很多高性能组件为了保证可预测的延迟会在启动时一次性分配好内存池然后用下标代替指针。链式前向星其实就是一张最简单的“内存池 链表”。理解了它以后再看到零拷贝序列化、内存池、对象池这些概念接受起来会顺畅很多。6.3 面试和考研遇到它怎么回答才加分数据结构和算法面试中图的存图方式是一个高频考点。基础回答是“邻接矩阵 邻接表”这时候如果你能主动补一句“还有一种链式前向星”在稀疏图上空间更优面试官通常会眼前一亮。回答框架可以按这三点来存储结构三个数组head、to、nexthead[u]指向 u 的第一条出边next[i]指向同起点的下一条边。复杂度空间 O(V E)加边 O(1)遍历某点出边 O(deg(u))。适用场景稀疏图、算法竞赛、需要频繁正向和反向边修改的网络流场景。考研数据结构笔试中如果出现代码填空题通常考的是addEdge函数和遍历模板。答题时注意初始化数组、边下标从几开始、终止条件用什么这些细节都要和题目的变量名一致不要盲目套用自己习惯的模板。一个我个人的答题技巧如果笔试里没有给出head初始化方式默认写memset(head, -1, sizeof(head))并让cnt 0。这是流传最广、判卷老师最不容易挑错的写法。如果真的遇到head初始化成 0 的版本遍历终止条件就是i ! 0不要搞混。链式前向星还有一个容易被面试官追问的细节它为什么叫“链式”答案在于它用next数组显式地维护了“同一顶点出边”的逻辑顺序不依赖数组下标的物理连续性从而避免了前向星排序的麻烦。这个点如果你能主动说出来基本就是满分回答了。最后说一点我自己的体会。很多人学链式前向星时觉得它不如 vector 邻接表直观于是直接跳过用熟了 vector 就不愿意再碰。但在真实的高性能场景里这个“不直观”的代价是值得的。我后来在做一个需要频繁遍历超大稀疏图的离线分析工具时迁移到链式前向星后内存峰值下降明显整体耗时也降了一截。数据结构这东西多一种选择永远比少一种好。你不需要每个项目都用它但你需要知道当 vector 和邻接矩阵都不太对劲的时候还有这么一个又小又快的老朋友在那里。