邻接表存储图：从原理到C++实现与性能优化

1. 为什么我们还在聊邻接表如果你写过图论相关的题目或者工程代码大概率绕不开一个最基础的抉择图到底怎么存。邻接矩阵和邻接表是两条最常走的路前者用二维数组一把梭后者用链表或者动态数组把边挂到每个顶点上。我见过不少刚接触图论的朋友上来就用邻接矩阵开一个1005 x 1005的数组结果点稍微多一点内存就爆了或者稀疏图里遍历邻居时白白扫了一整行零。这时候邻接表的价值就体现出来了。这篇文章我想把基于邻接表的图的储存这件事从头到尾讲透不只是贴一段能跑的 C 代码而是把设计思路、内存布局、边的插入顺序、遍历方式、常见坑点都拆开揉碎。适合正在学数据结构的学生、准备算法竞赛的选手也适合工作中需要手写图结构的开发者。读完你应该能自己从零实现一份稳定、好扩展的邻接表并且知道什么时候该用它、什么时候该换别的结构。先说清楚邻接表的核心思想对于图中的每个顶点我们维护一个容器里面存放所有从它出发能直接到达的邻居。无向图里一条边会在两个顶点的容器里各出现一次有向图里只出现在起点的容器里。这个容器可以是链表、std::vector、甚至哈希表选哪种直接决定了代码风格和性能特征。下面我会以最通用的vector实现为主线同时对比链表写法的取舍。2. 邻接表的核心设计与选型思路2.1 邻接矩阵的痛点在哪里要理解邻接表为什么存在先看邻接矩阵的问题。假设图有 n 个顶点邻接矩阵固定占用 n² 个存储单元。对于稠密图比如 n1000 且边数接近 n²/2这个开销是合理的因为几乎每个位置都有边。但现实中的图大多是稀疏的社交网络里一个人平均好友数远小于总人数道路网里一个路口连接的道路也就几条。这时候 n² 里绝大多数格子是 0空间浪费极其严重。除了空间遍历邻居的效率也是问题。用邻接矩阵找某个顶点的所有邻居必须扫描整行 n 个元素时间复杂度 O(n)而实际邻居可能只有几个。邻接表把这件事降到 O(degree)degree 是该顶点的度数也就是真实邻居数量。在稀疏图里这个差距是数量级的。注意邻接矩阵并非一无是处。判断两点之间是否有边矩阵是 O(1)邻接表平均是 O(degree)。所以稠密图或者频繁查询任意两点连通性的场景矩阵反而更合适。选型要看具体需求不要无脑上邻接表。2.2 邻接表的三种常见实现形态第一种是纯链表每个顶点挂一个单链表节点动态new出来。这种写法最贴近教科书定义插入边是 O(1)但每个节点都有指针开销缓存局部性差而且频繁new/delete容易产生内存碎片。我早期写竞赛代码时用这种后来基本弃用了。第二种是vector的数组也就是vectorint adj[n]或者vectorvectorint 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; }或者pairint,int。我个人的习惯是定义一个Edge结构体字段名写清楚比pair可读性好很多调试时也方便。这里有个容易忽略的点如果图里可能有重边邻接表天然支持同一个邻居会出现多次。有些算法需要去重有些不需要取决于题目要求。比如求最短路时重边无所谓取最小权值即可但求生成树时重边可能导致重复计算需要提前处理。3. 手把手实现一份可复用的邻接表3.1 基础版本vector 数组实现先给一份最朴素但足够好用的实现。假设顶点编号从 0 到 n-1边不带权。#include vector #include iostream using namespace std; class Graph { private: int n; // 顶点数 vectorvectorint 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; vectorvectorEdge 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 开始。两种处理方式一是开 n1 大小下标 0 空着不用二是每次输入减一。我倾向于开 n1代码里不用到处减一减少出错概率。代价是浪费一个位置可以忽略不计。Graph g(n 1); // 顶点编号 1..n g.addUndirectedEdge(u, v); // 直接用原编号4. 遍历、度数与实际应用场景4.1 深度优先与广度优先遍历邻接表最直接的用途就是图的遍历。DFS 用递归或栈BFS 用队列核心都是拿到一个顶点后遍历它的邻居列表。vectorbool visited; void dfs(int u) { visited[u] true; for (int v : adj[u]) { if (!visited[v]) { dfs(v); } } } void bfs(int start) { queueint 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 递归深度可能达到 nn 很大时会栈溢出这时候要么改迭代写法要么手动开栈。我踩过这个坑一次 n10^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((nm) log n)比邻接矩阵的 O(n²) 在稀疏图上快得多。拓扑排序靠遍历每个顶点的出边来减入度。求连通分量就是反复 DFS 或 BFS 标记未访问的顶点。以拓扑排序为例核心逻辑是维护入度数组把入度为 0 的点入队每次出队一个点就遍历它的邻居把邻居入度减一减到 0 就入队。vectorint topoSort(int n, vectorvectorint adj) { vectorint indeg(n, 0); for (int u 0; u n; u) { for (int v : adj[u]) { indeg[v]; } } queueint q; for (int i 0; i n; i) { if (indeg[i] 0) q.push(i); } vectorint 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 内存估算与容器选择假设 n10^5m2×10^5用vectorvectorint每个vector对象本身约 24 字节n 个就是 2.4MB加上边数据 2×10^5×4 字节约 0.8MB总共 3MB 出头完全可控。如果用vectorvectorEdge且 Edge 含两个 int边数据翻倍到 1.6MB也还好。链式前向星用几个 int 数组总内存约 (n2m)×4 字节更紧凑。真正要小心的是 n 达到 10^6 且用vector数组时光是 vector 对象本身就有 24MB加上边数据可能超限。这时候链式前向星或者压缩存储更合适。6. 几个容易被忽略的实操细节6.1 输入规模大时用快速 IOC 的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 的避免重复。vectorpairint,int toEdgeList(int n, vectorvectorint adj) { vectorpairint,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的接口。这样既有一层抽象方便复用又不会因为过度封装影响性能或者调试。竞赛时我通常直接用全局的vectorvectorint adj工程里才包成类。场景不同取舍不同没有绝对的对错。