1. 为什么我们还在聊邻接表
如果你写过图论相关的题目或者工程代码，大概率绕不开一个最基础的抉择：图到底怎么存。邻接矩阵和邻接表是两条最常走的路，前者用二维数组一把梭，后者用链表或者动态数组把边挂到每个顶点上。我见过不少刚接触图论的朋友，上来就用邻接矩阵开一个1005 x 1005的数组，结果点稍微多一点内存就爆了，或者稀疏图里遍历邻居时白白扫了一整行零。这时候邻接表的价值就体现出来了。
这篇文章我想把基于邻接表的图的储存这件事从头到尾讲透，不只是贴一段能跑的 C++ 代码，而是把设计思路、内存布局、边的插入顺序、遍历方式、常见坑点都拆开揉碎。适合正在学数据结构的学生、准备算法竞赛的选手，也适合工作中需要手写图结构的开发者。读完你应该能自己从零实现一份稳定、好扩展的邻接表，并且知道什么时候该用它、什么时候该换别的结构。
先说清楚邻接表的核心思想：对于图中的每个顶点，我们维护一个容器，里面存放所有从它出发能直接到达的邻居。无向图里一条边会在两个顶点的容器里各出现一次，有向图里只出现在起点的容器里。这个容器可以是链表、std::vector、甚至哈希表，选哪种直接决定了代码风格和性能特征。下面我会以最通用的vector实现为主线，同时对比链表写法的取舍。
2. 邻接表的核心设计与选型思路
2.1 邻接矩阵的痛点在哪里
要理解邻接表为什么存在，先看邻接矩阵的问题。假设图有 n 个顶点，邻接矩阵固定占用 n² 个存储单元。对于稠密图，比如 n=1000 且边数接近 n²/2，这个开销是合理的，因为几乎每个位置都有边。但现实中的图大多是稀疏的：社交网络里一个人平均好友数远小于总人数，道路网里一个路口连接的道路也就几条。这时候 n² 里绝大多数格子是 0，空间浪费极其严重。
除了空间，遍历邻居的效率也是问题。用邻接矩阵找某个顶点的所有邻居，必须扫描整行 n 个元素，时间复杂度 O(n)，而实际邻居可能只有几个。邻接表把这件事降到 O(degree)，degree 是该顶点的度数，也就是真实邻居数量。在稀疏图里这个差距是数量级的。
注意：邻接矩阵并非一无是处。判断两点之间是否有边，矩阵是 O(1)，邻接表平均是 O(degree)。所以稠密图或者频繁查询任意两点连通性的场景，矩阵反而更合适。选型要看具体需求，不要无脑上邻接表。
2.2 邻接表的三种常见实现形态
第一种是纯链表，每个顶点挂一个单链表，节点动态new出来。这种写法最贴近教科书定义，插入边是 O(1)，但每个节点都有指针开销，缓存局部性差，而且频繁new/delete容易产生内存碎片。我早期写竞赛代码时用这种，后来基本弃用了。
第二种是vector的数组，也就是vector<int> adj[n]或者vector<vector<int>> adj(n)。每个顶点的邻居存在一个连续内存的动态数组里，插入用push_back，遍历用范围 for。这是目前最推荐的写法，代码短、缓存友好、不容易出错。缺点是vector扩容时会有内存重分配，但均摊下来仍是 O(1)。
第三种是前向星，也叫链式前向星。它用几个平行数组head[]、to[]、next[]来模拟链表，完全避免动态内存，所有边存在连续数组里。这种写法在竞赛里非常流行，因为常数小、可控性强，但可读性差一些，新手容易写错下标。
| 实现方式 | 空间开销 | 插入边 | 遍历邻居 | 可读性 | 适用场景 |
|---|---|---|---|---|---|
| 纯链表 | 每节点含指针 | O(1) | O(degree) | 中 | 教学演示 |
| vector 数组 | 紧凑 | 均摊 O(1) | O(degree) | 高 | 通用首选 |
| 链式前向星 | 最紧凑 | O(1) | O(degree) | 低 | 竞赛性能敏感 |
2.3 有向图、无向图与带权图的统一处理
邻接表最舒服的一点是这三种图可以用同一套骨架。无向图插入边 (u, v) 时，在adj[u]和adj[v]各加一次；有向图只在adj[u]加一次。带权图则把容器元素从int换成struct Edge { int to, weight; }或者pair<int,int>。我个人的习惯是定义一个Edge结构体，字段名写清楚，比pair可读性好很多，调试时也方便。
这里有个容易忽略的点：如果图里可能有重边，邻接表天然支持，同一个邻居会出现多次。有些算法需要去重，有些不需要，取决于题目要求。比如求最短路时重边无所谓，取最小权值即可；但求生成树时重边可能导致重复计算，需要提前处理。
3. 手把手实现一份可复用的邻接表
3.1 基础版本：vector 数组实现
先给一份最朴素但足够好用的实现。假设顶点编号从 0 到 n-1，边不带权。
#include <vector> #include <iostream> using namespace std; class Graph { private: int n; // 顶点数 vector<vector<int>> adj; // 邻接表 public: Graph(int n) : n(n), adj(n) {} // 添加有向边 u -> v void addDirectedEdge(int u, int v) { adj[u].push_back(v); } // 添加无向边 u - v void addUndirectedEdge(int u, int v) { adj[u].push_back(v); adj[v].push_back(u); } // 遍历某个顶点的所有邻居 void printNeighbors(int u) { cout << u << " 的邻居: "; for (int v : adj[u]) { cout << v << " "; } cout << endl; } };这段代码里adj(n)在构造函数里一次性分配了 n 个空 vector，之后每次push_back只影响对应顶点。addUndirectedEdge插两次是标准做法，别偷懒只插一次，否则遍历会漏。
3.2 带权版本：结构体存边
带权图把int换成结构体。我建议给结构体写个构造函数，省得每次初始化都写一堆花括号。
struct Edge { int to; int weight; Edge(int t, int w) : to(t), weight(w) {} }; class WeightedGraph { private: int n; vector<vector<Edge>> adj; public: WeightedGraph(int n) : n(n), adj(n) {} void addDirectedEdge(int u, int v, int w) { adj[u].emplace_back(v, w); } void addUndirectedEdge(int u, int v, int w) { adj[u].emplace_back(v, w); adj[v].emplace_back(u, w); } };用emplace_back而不是push_back，可以直接在容器尾部构造对象，少一次临时对象的拷贝。这个细节在边数很大时能省一点开销，虽然现代编译器优化后差距不大，但养成习惯没坏处。
3.3 链式前向星版本：性能敏感场景的备选
如果边数达到百万级，或者你在打竞赛卡常数，链式前向星值得掌握。核心是用数组模拟链表，head[u]存 u 的第一条边在边数组里的下标，next[i]存第 i 条边的下一条边下标。
const int MAXN = 100005; const int MAXM = 200005; int head[MAXN], to[MAXM], nxt[MAXM], weight[MAXM]; int edgeCnt = 0; void init() { fill(head, head + MAXN, -1); edgeCnt = 0; } void addEdge(int u, int v, int w) { to[edgeCnt] = v; weight[edgeCnt] = w; nxt[edgeCnt] = head[u]; head[u] = edgeCnt++; } // 遍历 u 的所有邻居 void traverse(int u) { for (int i = head[u]; i != -1; i = nxt[i]) { int v = to[i]; int w = weight[i]; // 处理边 u -> v，权值 w } }注意无向图时MAXM要开边数的两倍，因为每条边要存两次。head初始化为 -1 表示没有边。这种写法插入是头插法，所以遍历顺序和插入顺序相反，如果对顺序有要求要注意。
提示：链式前向星的下标从 0 开始，
edgeCnt每加一条边自增。无向图调用两次addEdge，一次 u 到 v，一次 v 到 u。
3.4 顶点编号从 1 开始时怎么处理
很多题目顶点编号是 1 到 n，而数组下标从 0 开始。两种处理方式：一是开 n+1 大小，下标 0 空着不用；二是每次输入减一。我倾向于开 n+1，代码里不用到处减一，减少出错概率。代价是浪费一个位置，可以忽略不计。
Graph g(n + 1); // 顶点编号 1..n g.addUndirectedEdge(u, v); // 直接用原编号4. 遍历、度数与实际应用场景
4.1 深度优先与广度优先遍历
邻接表最直接的用途就是图的遍历。DFS 用递归或栈，BFS 用队列，核心都是拿到一个顶点后遍历它的邻居列表。
vector<bool> visited; void dfs(int u) { visited[u] = true; for (int v : adj[u]) { if (!visited[v]) { dfs(v); } } } void bfs(int start) { queue<int> q; visited[start] = true; q.push(start); while (!q.empty()) { int u = q.front(); q.pop(); for (int v : adj[u]) { if (!visited[v]) { visited[v] = true; q.push(v); } } } }这里visited数组大小要和顶点数匹配。DFS 递归深度可能达到 n，n 很大时会栈溢出，这时候要么改迭代写法，要么手动开栈。我踩过这个坑，一次 n=10^5 的链状图直接让递归爆栈，排查了半天才发现是深度问题。
4.2 度数统计与孤立点识别
无向图里顶点的度数就是adj[u].size()，有向图里出度是adj[u].size()，入度需要额外统计或者反向建图。孤立点就是adj[u].empty()为真的顶点。这些操作在邻接表里都是 O(1) 或 O(degree)，非常自然。
int degree(int u) { return adj[u].size(); // 无向图度数 } bool isIsolated(int u) { return adj[u].empty(); }如果要统计整个图的边数，无向图把所有顶点的度数加起来除以 2，有向图直接加起来就是边数。这个在验证输入数据时很有用。
4.3 典型应用：最短路、拓扑排序、连通分量
邻接表是这些算法的标准输入结构。Dijkstra 用邻接表加优先队列，复杂度 O((n+m) log n)，比邻接矩阵的 O(n²) 在稀疏图上快得多。拓扑排序靠遍历每个顶点的出边来减入度。求连通分量就是反复 DFS 或 BFS 标记未访问的顶点。
以拓扑排序为例，核心逻辑是维护入度数组，把入度为 0 的点入队，每次出队一个点就遍历它的邻居，把邻居入度减一，减到 0 就入队。
vector<int> topoSort(int n, vector<vector<int>>& adj) { vector<int> indeg(n, 0); for (int u = 0; u < n; u++) { for (int v : adj[u]) { indeg[v]++; } } queue<int> q; for (int i = 0; i < n; i++) { if (indeg[i] == 0) q.push(i); } vector<int> order; while (!q.empty()) { int u = q.front(); q.pop(); order.push_back(u); for (int v : adj[u]) { if (--indeg[v] == 0) q.push(v); } } return order; // 若大小小于 n 说明有环 }这段代码里入度统计需要遍历所有边，所以建图时如果同时维护入度数组可以省一次遍历。工程里我通常在建图函数里顺手更新入度。
5. 常见问题与排查技巧实录
5.1 数组越界与顶点编号混淆
最常见的 bug 就是顶点编号从 1 开始但数组开了 n 大小，访问adj[n]直接越界。或者无向图只插了一次边，导致遍历时单向可达。排查方法很简单：先打印顶点数和边数，再逐个打印每个顶点的邻居列表，和输入对照。
| 问题现象 | 可能原因 | 排查方法 |
|---|---|---|
| 程序崩溃或乱码 | 数组越界 | 检查顶点编号范围与数组大小 |
| 遍历漏掉部分点 | 无向图只插一次边 | 确认 addEdge 调用次数 |
| 结果与预期不符 | 重边或自环未处理 | 打印边列表检查输入 |
| 递归爆栈 | DFS 深度过大 | 改迭代或增大栈空间 |
| 内存超限 | 容器开太大或边存重复 | 估算 n 和 m 的实际规模 |
5.2 性能问题：vector 扩容与缓存
vector在push_back时如果容量不够会重新分配内存，把旧元素搬过去。虽然均摊 O(1)，但频繁扩容仍有开销。如果提前知道每个顶点的度数，可以用reserve预分配。不过大多数场景下没必要，除非你在极致优化。
另一个性能点是遍历顺序。vector里元素连续存储，顺序遍历缓存命中率高。链式前向星虽然也连续，但通过nxt跳转，访问模式是链式的，缓存表现略差。实测在百万边规模下，vector版本通常更快，除非内存极度受限。
5.3 自环与重边的处理策略
自环就是 u 到 u 的边。无向图里自环会让度数加 2，有些算法需要特殊处理。重边是同一对顶点之间多条边。如果题目不保证无重边，建图时可以选择去重，但去重本身有开销。我的经验是：先看题目要求，如果算法对重边不敏感就别去重，省时间；如果敏感，用set或者排序后去重。
注意：Dijkstra 遇到重边不用去重，因为优先队列会自然取最小。但求最小生成树时重边可能导致同一对顶点被多次考虑，不过 Kruskal 排序后取最小边即可，也不一定要去重。
5.4 内存估算与容器选择
假设 n=10^5，m=2×10^5，用vector<vector<int>>，每个vector对象本身约 24 字节，n 个就是 2.4MB，加上边数据 2×10^5×4 字节约 0.8MB，总共 3MB 出头，完全可控。如果用vector<vector<Edge>>且 Edge 含两个 int，边数据翻倍到 1.6MB，也还好。链式前向星用几个 int 数组，总内存约 (n+2m)×4 字节，更紧凑。
真正要小心的是 n 达到 10^6 且用vector数组时，光是 vector 对象本身就有 24MB，加上边数据可能超限。这时候链式前向星或者压缩存储更合适。
6. 几个容易被忽略的实操细节
6.1 输入规模大时用快速 IO
C++ 的cin/cout默认和 C 的stdio同步，速度较慢。边数上百万时，输入输出可能成为瓶颈。加一行ios::sync_with_stdio(false); cin.tie(nullptr);能显著提速。我实测过，同样的数据，加了这两行从 1.2 秒降到 0.3 秒。
int main() { ios::sync_with_stdio(false); cin.tie(nullptr); // 后续用 cin/cout }6.2 多组测试数据的清空问题
如果程序要处理多组测试，每轮都要清空邻接表。vector用clear()只清元素不释放容量，下一轮复用容量反而更快。但如果是全局数组的链式前向星，记得重置head和edgeCnt。我见过有人忘了重置edgeCnt，导致第二组数据边下标错乱。
6.3 调试时打印图结构
调试图算法时，先把图打印出来能省很多时间。写一个printGraph函数，逐行输出每个顶点和它的邻居。
void printGraph() { for (int u = 0; u < n; u++) { cout << u << ": "; for (int v : adj[u]) cout << v << " "; cout << "\n"; } }小图直接看，大图可以只打印前几个顶点或者统计度数分布。
6.4 从邻接表反推边列表
有时候需要把邻接表转回边列表，比如输出所有边或者做边排序。无向图要注意每条边会出现两次，转换时只取 u < v 的避免重复。
vector<pair<int,int>> toEdgeList(int n, vector<vector<int>>& adj) { vector<pair<int,int>> edges; for (int u = 0; u < n; u++) { for (int v : adj[u]) { if (u < v) edges.push_back({u, v}); // 无向图去重 } } return edges; }有向图则不需要u < v判断，直接全部加入。
7. 从邻接表延伸出去的几个方向
邻接表本身不复杂，但它是很多高级结构的起点。比如反向建图，把每条边方向反过来存一份，用于需要同时访问入边和出边的算法。再比如带删除边的动态图，可以用set代替vector存邻居，删除是 O(log degree)。还有网络流里的残量网络，本质也是邻接表加反向边，每条边存一个反向边的下标，增广时同时更新正反两条边。
我个人的体会是，把邻接表写熟之后，再学这些扩展会顺很多。因为核心操作就是插入边、遍历邻居、访问权值，变来变去都是在这三件事上做文章。真正要花心思的是根据问题特点选对容器和存储方式，以及在性能、内存、可读性之间找到平衡点。
最后分享一个我常用的模板习惯：把建图和遍历封装成类，但保留直接访问adj的接口。这样既有一层抽象方便复用，又不会因为过度封装影响性能或者调试。竞赛时我通常直接用全局的vector<vector<int>> adj，工程里才包成类。场景不同，取舍不同，没有绝对的对错。
