企业官网建设流程全解析

1. 为什么邻接表是图存储的“万金油”方案

1.1 从一次内存告警说起

几年前我接手过一个社交关系分析的小工具，需要处理一份大约五十万个节点、平均每个节点连接几十个邻居的图数据。当时想都没想就用了邻接矩阵，vector<vector<int>>开出来，编译通过，跑起来直接内存告警。算一笔账就明白了：五十万个节点，邻接矩阵就是 50万 × 50万 个整型槽位，哪怕每个int只占 4 字节，那也是接近 10^12 字节的量级，也就是 TB 级别。而实际上这份图里真正存在的边只有几千万条，绝大多数矩阵格子都是空的。这就是典型的稠密表示存稀疏数据，浪费得离谱。

换成邻接表之后，内存占用直接掉到几十 MB 的量级，程序跑得飞快。从那以后，只要图的边数远小于节点数的平方（也就是稀疏图），我基本都会优先考虑邻接表。这篇文章就把基于邻接表的图存储从原理到 C++ 实现完整讲一遍，包括数组模拟和vector两种写法、有向图无向图的区别、带权边的处理，以及我在实际写代码时踩过的那些坑。适合正在学数据结构、准备算法竞赛，或者要在工程里手写图结构的同学参考。

1.2 邻接表到底“表”在哪里

很多人第一次听到“邻接表”会以为是某种表格，其实它本质上是每个节点挂一条链表（或动态数组），链表里存的是这个节点能直接到达的所有邻居。你可以把它想象成通讯录：每个人（节点）手里有一份名单，名单上写着他能直接联系到的人（邻居）。要找“A 能不能到 B”，就去翻 A 的名单；要遍历 A 的所有朋友，就把 A 的名单从头到尾走一遍。

这种结构的好处非常直接：空间只和“实际存在的边数”成正比。有 V 个节点、E 条边的图，邻接表的空间复杂度是 O(V + E)，而邻接矩阵是 O(V²)。对于稀疏图，这两者差距是数量级的。代价是查询“u 和 v 之间是否有边”时，邻接表需要遍历 u 的邻居列表，最坏 O(度数)，而邻接矩阵是 O(1)。所以选哪个，取决于你的图是稀疏还是稠密，以及你最频繁的操作是“遍历邻居”还是“判断两点是否相邻”。

1.3 两种主流实现路线

在 C++ 里实现邻接表，我常用的有两条路线，各有适用场景：

• vector嵌套路线：vector<vector<int>> adj，或者带权时用vector<vector<pair<int,int>>>。写起来直观，动态扩容方便，适合节点数不确定、需要频繁增删边的场景，也是工程代码里最常见的写法。
• 数组模拟链式前向星路线：用head[]、to[]、next[]、w[]几个数组手动模拟链表。常数小、缓存友好、没有动态内存开销，是算法竞赛里处理大规模图的首选。

下面我会把两条路线都讲透，并且给出可以直接抄的完整代码。先讲清楚设计思路，再落到具体实现，最后集中说排查技巧。

2. 邻接表的核心设计与选型考量

2.1 有向图、无向图、带权图分别怎么存

这是新手最容易搞混的地方，我把它拆开说。

有向图：一条边 u → v，只在 u 的邻居列表里加一个 v。存一次就够了。

无向图：一条边 u — v，等价于 u → v 和 v → u 两条有向边。所以要在 u 的列表里加 v，同时在 v 的列表里加 u。存两次。这一点如果忘了，遍历的时候就会发现“从 A 能到 B，但从 B 回不到 A”，非常隐蔽。

带权图：邻居列表里不能只存“邻居是谁”，还要存“这条边的权重是多少”。所以每个表项变成一个二元组(邻居, 权重)。无向带权图同样要存两次，两次的权重相同。

我用一个表格把四种组合列清楚，方便对照：

提示：判断该存一次还是两次，就问自己一句话——“这条边是单向的还是双向的”。单向存一次，双向存两次，没有例外。

2.2 节点编号从 0 还是从 1 开始

这个问题看似小，实则影响后面所有代码的边界处理。我的建议是：看题目或业务给的编号习惯。算法题里经常是 1 到 n，工程里经常是 0 到 n-1。

如果输入是 1 到 n，你有两个选择：要么把数组开成 n+1 大小，下标 1 到 n 直接用；要么读入时统一减一，转成 0 到 n-1。前者写起来省事，代价是浪费一个下标 0 的空间；后者更“干净”，但每次读入都要记得减一，容易漏。

我个人的习惯是：算法竞赛用 n+1 开数组，工程代码统一转 0 基。因为竞赛追求写得快、少出错，多开一个空间无所谓；工程代码讲究一致性，0 基更符合 C++ 的数组习惯。

2.3 为什么数组模拟比 vector 快

很多人会问，vector写起来那么舒服，为什么竞赛里还要用数组模拟？核心原因是内存局部性和动态开销。

vector<vector<int>>里，外层 vector 存的是一个个内层 vector 对象，每个内层 vector 的底层数据是分散在堆上的。遍历图的时候，CPU 缓存命中率低，因为邻居数据不连续。而数组模拟的链式前向星，所有边都紧凑地存在to[]、next[]这几个连续数组里，遍历时缓存友好，常数能小好几倍。

另外，vector的push_back在扩容时会重新分配内存、拷贝数据，虽然均摊是 O(1)，但在极端数据量下会有抖动。数组模拟则是预先开好固定大小，完全没有动态分配。

所以结论是：数据量小、图结构动态变化，用 vector；数据量大、图结构固定，用数组模拟。这不是教条，是我实测下来的经验。

3. vector 嵌套实现：最直观的邻接表写法

3.1 无权图的基础框架

先看最基础的版本，不带权、有向图：

#include <vector> using namespace std; int n; // 节点数 vector<vector<int>> adj; // adj[u] 存 u 的所有邻居 void init(int nodeCount) { n = nodeCount; adj.assign(n, vector<int>()); // 清空并分配 n 个空列表 } void addEdge(int u, int v) { adj[u].push_back(v); // 有向图只加一次 } void addUndirectedEdge(int u, int v) { adj[u].push_back(v); adj[v].push_back(u); // 无向图加两次 }

这段代码里，adj.assign(n, vector<int>())是关键。它把adj重置成 n 个空的 vector，比adj.clear()再循环resize更简洁，也比重新构造一个对象更省事。如果你确定只初始化一次，直接vector<vector<int>> adj(n);也行。

遍历 u 的所有邻居就是：

for (int v : adj[u]) { // 处理邻居 v }

这种写法可读性极高，是我在工程里最常用的形式。

3.2 带权图的 pair 写法

带权图把int换成pair<int,int>，第一个元素是邻居，第二个是权重：

#include <vector> #include <utility> using namespace std; vector<vector<pair<int,int>>> adj; // (邻居, 权重) void init(int n) { adj.assign(n, vector<pair<int,int>>()); } void addEdge(int u, int v, int w) { adj[u].push_back({v, w}); // 有向带权 } void addUndirectedEdge(int u, int v, int w) { adj[u].push_back({v, w}); adj[v].push_back({u, w}); // 无向带权，权重相同 }

遍历时用结构化绑定（C++17）会非常清爽：

for (auto [v, w] : adj[u]) { // v 是邻居，w 是边权 }

如果你的编译器不支持 C++17，就老老实实写for (auto& e : adj[u])，然后用e.first和e.second。

注意：pair的默认比较是先比 first 再比 second。如果你要对邻居排序，带权图排序时会先按邻居编号排，邻居相同再按权重排。这个特性有时候有用，有时候会坑你，心里要有数。

3.3 一个完整的可运行示例

光看片段不够，我给一个完整能跑的，用 BFS 求无权图最短路径（边数最少）：

#include <bits/stdc++.h> using namespace std; int main() { int n = 6; vector<vector<int>> adj(n); // 建一个无向图 auto addUndirected = [&](int u, int v) { adj[u].push_back(v); adj[v].push_back(u); }; addUndirected(0, 1); addUndirected(0, 2); addUndirected(1, 3); addUndirected(2, 3); addUndirected(3, 4); addUndirected(4, 5); // BFS 求 0 到各点的最短边数 vector<int> dist(n, -1); queue<int> q; dist[0] = 0; q.push(0); while (!q.empty()) { int u = q.front(); q.pop(); for (int v : adj[u]) { if (dist[v] == -1) { dist[v] = dist[u] + 1; q.push(v); } } } for (int i = 0; i < n; i++) { cout << "0 -> " << i << " : " << dist[i] << "\n"; } return 0; }

这段代码把建图、遍历、BFS 串起来了，你可以直接复制去跑。输出会告诉你从节点 0 到每个节点的最少边数。注意dist初始化为 -1 表示未访问，这是 BFS 的标准套路。

4. 数组模拟链式前向星：竞赛级的高效实现

4.1 四个数组各司其职

链式前向星这个名字听着唬人，其实就是用数组模拟链表。核心是四个数组：

• head[u]：节点 u 的“第一条边”在边数组里的下标，初始为 -1。
• to[i]：第 i 条边指向的邻居节点。
• nxt[i]：第 i 条边的“下一条边”的下标，形成链表。
• w[i]：第 i 条边的权重（无权图可以省掉）。

加一条边 u → v 的过程是：把新边放到数组末尾（下标idx），让它的to指向 v，让它的nxt指向head[u]（也就是 u 原来那条链表的头），最后把head[u]更新成idx。这本质上是头插法建链表。

4.2 加边函数的实现与图解

const int MAXN = 100005; // 最大节点数 const int MAXM = 200005; // 最大边数（无向图要开两倍） int head[MAXN]; int to[MAXM], nxt[MAXM], w[MAXM]; int idx = 0; // 当前边的编号 void init() { memset(head, -1, sizeof(head)); // head 全部置 -1 idx = 0; } void addEdge(int u, int v, int weight) { to[idx] = v; w[idx] = weight; nxt[idx] = head[u]; // 新边指向 u 原来的第一条边 head[u] = idx; // u 的第一条边更新为新边 idx++; }

无向图就调用两次addEdge：

void addUndirectedEdge(int u, int v, int weight) { addEdge(u, v, weight); addEdge(v, u, weight); }

我用一个具体例子说明链表是怎么串起来的。假设依次加边 0→1、0→2、0→3：

• 加 0→1：idx=0，to[0]=1，nxt[0]=head[0]=-1，head[0]=0。
• 加 0→2：idx=1，to[1]=2，nxt[1]=head[0]=0，head[0]=1。
• 加 0→3：idx=2，to[2]=3，nxt[2]=head[0]=1，head[0]=2。

现在从head[0]=2出发：2 →nxt[2]=1→nxt[1]=0→nxt[0]=-1结束。遍历顺序是 3、2、1，正好和加边顺序相反。这就是头插法的特点——后加的边先被遍历到。如果你对遍历顺序有要求，要么调整加边顺序，要么改用尾插（麻烦，不推荐）。

4.3 遍历邻居的标准写法

for (int i = head[u]; i != -1; i = nxt[i]) { int v = to[i]; int weight = w[i]; // 处理邻居 v 和边权 weight }

这个循环是链式前向星的灵魂，必须背下来。i从head[u]开始，每次跳到nxt[i]，直到 -1 结束。注意循环变量是边的下标，不是节点编号，别搞混。

提示：memset(head, -1, sizeof(head))只能把数组按字节置成 -1，因为 -1 的补码是全 1，所以对int数组有效。如果你想置成其他值（比如 0），也可以用 memset，但置成 1 就不行了，会得到 0x01010101。这个坑我见过太多人踩。

4.4 数组模拟的边界与容量计算

容量计算是链式前向星最容易出错的地方。规则很简单：

• 有向图：边数组大小 = 边数 M。
• 无向图：每条边存两次，边数组大小 = 2 × M。

我见过有人无向图只开了 M 的大小，结果加边加到一半idx越界，程序直接段错误或者更隐蔽地写坏内存。所以开数组时宁可多开一点，比如无向图直接开2*M + 5，留点余量。

另外，节点数如果达到 10^5 级别，head数组开MAXN没问题；但如果节点数动态变化，用vector<int> head(n, -1)更灵活。数组模拟不一定非要用全局定长数组，用 vector 承载同样能享受连续内存的好处。

5. 两种实现的性能对比与选型建议

5.1 实测数据说话

我在本地做过一组对比测试，图规模是 10 万节点、50 万条边，无向图，跑一遍完整的 DFS 遍历，统计耗时（同一台机器，多次取平均）：

差距主要来自两点：一是 vector 的动态扩容和堆分配开销，二是链式前向星的连续内存带来的缓存友好。数据量越大，差距越明显。到了百万级边，链式前向星的优势会非常突出。

5.2 什么时候用哪个

我的选型经验是这样的：

• 写工程、图结构会动态增删边、可读性优先：用vector嵌套。代码短、易维护、不容易出错。
• 算法竞赛、数据量大、追求极致性能：用链式前向星。常数小、内存可控。
• 需要频繁判断两点是否相邻：两者都不理想，考虑邻接矩阵或哈希表辅助。
• 图非常稠密（E 接近 V²）：邻接矩阵反而更合适，邻接表优势不明显。

注意：不要为了“性能”无脑上链式前向星。如果你的图只有几百个节点，vector 写法跑得一样快，可读性还高得多。过早优化是万恶之源，这句话在图存储上同样成立。

5.3 一个折中方案：vector 承载的链式前向星

如果你既想要链式前向星的性能，又不想用全局定长数组，可以用 vector 来承载：

vector<int> head, to, nxt, w; int idx = 0; void init(int n, int maxEdges) { head.assign(n, -1); to.resize(maxEdges); nxt.resize(maxEdges); w.resize(maxEdges); idx = 0; }

这样既保留了连续内存和头插法的效率，又避免了全局数组的僵硬。我在一些需要多组测试数据的场景里经常这么写，每次init重置即可。

6. 常见问题与排查技巧实录

6.1 遍历时漏掉节点或死循环

症状：DFS/BFS 结果不对，或者程序卡死。

排查思路：先检查无向图是不是只加了一次边。如果只加了一次，从某些节点出发就遍历不到它的“上游”邻居。再检查链式前向星的循环条件，是不是写成了i != 0而不是i != -1。head初始值是 -1，如果误用 0 作为终止条件，就会漏掉或死循环。

速查表：

6.2 数组越界与内存踩踏

链式前向星最常见的崩溃就是边数组开小了。无向图忘了开两倍，加边加到后面idx超过数组长度，写到了别的变量内存上，症状可能是“程序跑着跑着某个无关变量变了”，非常难查。

我的习惯是：开数组时先算清楚，无向图直接2*M+5，并且加边函数里加一句断言（调试期）：

void addEdge(int u, int v, int weight) { assert(idx < MAXM && "边数组越界！"); // ... }

上线前把断言关掉即可。这一句话帮我省了无数调试时间。

6.3 重边和自环的处理

实际数据里经常有重边（同样的 u→v 出现多次）和自环（u→u）。邻接表本身不排斥它们，会老老实实都存下来。如果你的算法不能容忍重边，需要在加边时判重，或者在建图后去重。

判重的简单办法是用set或哈希表记录已存在的边，但会增加开销。如果数据保证无重边，就别做无用功。自环在大多数最短路算法里无害（会被松弛逻辑自然忽略），但在某些计数问题里会导致答案翻倍，要特别小心。

6.4 大规模数据下的内存优化

当节点和边都到百万级，内存就成了瓶颈。几个优化方向：

• 用int而不是long long存节点编号和边下标，除非真的超过 21 亿。
• 无权图省掉w数组，直接省四分之一内存。
• 边权如果范围小，用short或int8_t，但要小心溢出。
• 考虑用 CSR（压缩稀疏行）格式，把邻接表压成两个数组，内存最省，但建图后不能动态改。

CSR 本质上是把链式前向星的链表“拉直”成连续数组，遍历更快，但只适合静态图。如果你的图建好就不改了，CSR 是终极方案。

7. 从邻接表延伸出去的实战场景

7.1 最短路、拓扑排序、连通分量

邻接表是这些经典算法的地基。Dijkstra 用带权邻接表加优先队列，拓扑排序用邻接表统计入度，Tarjan 求强连通分量用邻接表做 DFS。你把邻接表写对了，这些算法就是往上叠逻辑的事。

我特别想强调一点：Dijkstra 的优先队列里存的是(距离, 节点)，出队时要判断这个距离是不是已经过时（也就是“懒惰删除”）。这个细节和邻接表本身无关，但配合使用时经常有人忘，导致答案偏大。

7.2 图论建模的思维转换

很多问题表面上看不是图，但能建模成图。比如“单词接龙”把单词当节点、能接龙当边；“课程安排”把课程当节点、先修关系当边。这时候邻接表就是你手里的通用工具。我的经验是：先把问题抽象成“什么是什么节点、什么是什么边”，再决定用哪种图存储。抽象对了，剩下的就是套模板。

7.3 工程中的图结构封装

在工程代码里，我通常会把邻接表封装成一个类，提供addEdge、neighbors、hasEdge等接口，内部实现可以随时从 vector 换成链式前向星而不影响调用方。这样既保证了可维护性，又留了性能优化的空间。接口稳定、实现可变，这是工程和竞赛思维的一个明显区别。

class Graph { public: explicit Graph(int n) : adj_(n) {} void addEdge(int u, int v) { adj_[u].push_back(v); } const vector<int>& neighbors(int u) const { return adj_[u]; } private: vector<vector<int>> adj_; };

这个类很小，但把细节藏起来了。以后要换成 CSR，只改内部即可。

写到这里，关于邻接表的核心内容基本讲完了。最后分享一个我自己的小习惯：每次写完建图代码，我都会先用一个三五节点的小图手动跑一遍，把每个节点的邻居列表打印出来核对。这个动作花不了一分钟，但能挡掉后面九成的诡异 bug。图这种结构，肉眼验证一遍邻接关系，比事后调试划算得多。