1. 从“图”说起为什么我们需要关心它的存储如果你正在接触数据结构与算法或者涉足图神经网络、路径规划、社交网络分析等领域那么“图”这个概念你一定绕不开。它不像数组或链表那样直观但却是描述实体间复杂关系最强大的工具。简单来说图就是由一堆“点”顶点和连接这些点的“线”边组成的结构。现实世界中的很多问题都可以抽象成图社交网络里的人是点关注关系是边地图上的城市是点道路是边程序里的函数是点调用关系是边。理解了图是什么下一个最实际的问题就是我们怎么在计算机里把它“存”起来这个问题看似基础却直接决定了后续所有操作的效率。你写的图算法是跑1秒还是10秒可能就取决于你最初选择了哪种存储方式。今天我们就来彻底搞懂图的两种最经典、也最核心的存储形式邻接矩阵和邻接表。我会结合大量实际场景告诉你它们各自的脾气秉性以及在不同情况下你究竟该选哪一个。2. 邻接矩阵用“表格”来记录所有关系邻接矩阵可能是最符合直觉的一种存储方式。它的核心思想非常简单粗暴用一个二维数组矩阵来表示图中顶点之间的连接关系。2.1 邻接矩阵的构建原理与示例假设我们有一个包含4个顶点编号为0, 1, 2, 3的无向图边的情况如下0连接1和21连接0和32连接03连接1。用邻接矩阵存储我们会创建一个4x4的二维数组matrix。规则是如果顶点i和顶点j之间有边相连那么matrix[i][j]和matrix[j][i]的值就设为1对于无向图否则设为0。根据上面的边关系我们得到的邻接矩阵如下012300110110012100030100这个矩阵非常直观。你想知道顶点0和顶点2是否相连直接看matrix[0][2]值是1说明相连。想知道顶点2的邻居有哪些遍历matrix[2]这一行发现matrix[2][0]是1所以顶点2只有一个邻居顶点0。对于带权图比如地图上城市间的距离这个矩阵存储的就不是0或1了而是边的权重。没有边的情况可以用一个特殊值表示比如无穷大INF或者0如果权重本身都大于0的话。2.2 邻接矩阵的优势与适用场景邻接矩阵最大的优点就是“快”和“简单”。1. 查询速度极快判断任意两个顶点间是否存在边或者获取边的权重时间复杂度是 O(1)。你只需要一次数组索引操作。这在某些需要频繁进行边存在性检查的算法中非常有用。2. 实现简单直观代码实现上几乎没有任何“坑”就是一个二维数组的创建和读写。对于很多算法竞赛的题目或者快速原型验证用邻接矩阵能让你更专注于算法逻辑本身。3. 适合稠密图什么是稠密图就是图中边的数量接近顶点数量的平方。在这种情况下邻接矩阵的空间利用率很高因为几乎每个格子都被用上了。例如一个完全图每个顶点都与其他所有顶点相连用邻接矩阵存储就非常合适。4. 便于某些矩阵运算在图神经网络GNN中邻接矩阵是输入的重要部分。一些图论算法如利用矩阵乘法计算路径数量比如计算经过k条边从i到j的路径数也天然依赖于矩阵表示。2.3 邻接矩阵的致命短板当然邻接矩阵的缺点也同样突出而且往往在工程实践中更为致命。1. 空间消耗巨大这是它最被诟病的一点。存储一个n个顶点的图无论有多少条边你都需要一个n * n的矩阵。如果顶点数上万这在社交网络、推荐系统中很常见这个矩阵将占用数百兆甚至上G的内存其中绝大部分空间0值都被浪费了。对于存储结构使用邻接矩阵的题目如果节点数n小于10那完全没问题但如果n是10000这个矩阵就是1亿个元素很可能导致内存超限。2. 添加/删除顶点成本高动态图顶点和边会频繁增减是邻接矩阵的噩梦。增加一个顶点意味着必须重新分配一个更大的矩阵并将旧数据拷贝过去时间复杂度是 O(n²)。这在实际系统中通常是不可接受的。3. 遍历邻居效率低如果你想找出一个顶点的所有邻居即使它只有两三个邻居你也必须遍历矩阵中对应的整行n个元素时间复杂度是 O(n)。对于稀疏图边数远小于n²这做了大量无用功。注意很多初学者在实现时会混淆顶点索引从0开始还是从1开始。题目中常说“节点分别用1, 2, ... n表示”但在代码中我们通常用0到n-1作为数组下标。这时需要做一个简单的映射读取边(u, v)时将其存储到matrix[u-1][v-1]和matrix[v-1][u-1]。这个小细节没处理好会导致整个图的数据错位。3. 邻接表用“链表”来记录有效连接为了解决邻接矩阵的空间浪费问题邻接表应运而生。它的核心思想是只为每个顶点存储它真正连接出去的边。3.1 邻接表的实现方式剖析邻接表通常用一个数组或列表来实现数组的每个下标对应一个顶点而每个数组元素本身是一个链表或动态数组。这个链表里存储的就是该顶点的所有邻居顶点对于带权图可以存储邻居顶点和权重的组合。还是用刚才那个4个顶点的无向图为例它的邻接表结构看起来是这样的用链表或动态数组表示顶点0: [1, 2]顶点1: [0, 3]顶点2: [0]顶点3: [1]在代码中常用vectorvectorint adjList(n)C或ListInteger[] adjList new ArrayList[n]Java这样的结构来实现。每个内层列表存储对应顶点的邻居。3.2 邻接表的优势与为何成为主流邻接表几乎是为现代应用中的图尤其是稀疏图量身定做的。1. 空间效率极高它只存储实际存在的边。存储n个顶点和m条边的图邻接表所需的空间大致为 O(n m)。对于社交网络这种动辄数亿用户顶点、但平均每个用户只有几百个关注边的极端稀疏图邻接表节省的内存是天文数字。2. 遍历邻居效率高要找出一个顶点的所有邻居你只需要遍历它对应的那个链表时间复杂度是 O(degree(v))其中 degree(v) 是该顶点的邻居数。对于大多数顶点度数很小的图这比邻接矩阵的 O(n) 快得多。像BFS、DFS这类需要频繁遍历邻居的算法在邻接表上运行速度优势明显。3. 易于处理动态图添加一个新顶点只需在数组末尾添加一个空链表成本是 O(1)。添加一条新边只需在对应两个顶点的链表中插入新节点成本也很低。删除操作虽然需要查找但总体也比调整整个矩阵要高效。4. 天然适配多种算法绝大多数经典的图算法如Dijkstra最短路径、Prim最小生成树、拓扑排序等其标准实现和优化版本都是基于邻接表设计的。社区提供的算法库如NetworkX in Python, Boost Graph Library in C也大多以邻接表作为底层或主要接口。3.3 邻接表不容忽视的缺点没有完美的数据结构邻接表也有它的“阿喀琉斯之踵”。1. 查询边存在性慢判断顶点u和v之间是否有边你需要在u的邻居链表里线性查找v时间复杂度是 O(degree(u))。在最坏情况下比如u是那个连接了几乎所有顶点的“超级节点”这可能接近 O(n)。如果你需要频繁进行这样的查询邻接表可能成为瓶颈。这时可以结合哈希表进行优化例如用vectorunordered_setint但会牺牲一些空间和构建时间。2. 实现稍复杂且有“坑”相比于邻接矩阵的二维数组邻接表的实现需要处理动态数据结构链表或动态数组。对于无向图添加一条边 (u, v) 时必须记得同时更新u的邻居列表和v的邻居列表。这个看似简单的步骤却是很多初学者调试时的噩梦——因为只更新一边会导致图的数据不一致进而让后续算法产生诡异的结果。3. 对缓存不友好链表中的节点在内存中可能是分散存储的遍历时会造成较多的缓存缺失Cache Miss影响性能。使用动态数组如C的vector替代链表可以缓解这个问题因为数组内存是连续的。这也是为什么在实际工程中vectorvectorpairint, int存储邻居和权重比真正的链表邻接表更常见。4. 实战场景下的选择策略与性能考量了解了两种存储方式的原理和优缺点后最关键的问题是我到底该用哪个这个选择没有标准答案完全取决于你的具体场景。4.1 场景一稠密图与小规模图 - 优先考虑邻接矩阵典型场景算法竞赛中的小图题目题目明确说明“节点数n(小于10个)”这几乎是在暗示你用邻接矩阵。代码简单不易出错在n很小时空间开销可忽略不计。图神经网络GNN的输入许多GNN框架如PyTorch Geometric底层计算需要邻接矩阵的稀疏或稠密表示来进行矩阵运算。虽然大规模图会用稀疏格式但思想源自邻接矩阵。需要频繁判断边是否存在例如在某些博弈论或状态转移模型中需要快速查询两个状态是否可达。实操建议如果顶点数在几百以内且图比较稠密放心使用邻接矩阵。用二维数组实现清晰明了。4.2 场景二稀疏图与大规模图 - 邻接表是唯一选择典型场景社交网络分析用户数巨大但平均好友数有限。网络拓扑与路由路由器作为顶点连接作为边。路径规划与导航交叉路口作为顶点道路作为边城市路网是典型的稀疏图。知识图谱实体数庞大但关系相对有限。实操建议绝大多数实际工程问题都属于这一类。强烈建议使用“动态数组”版本的邻接表而不是真正的链表。以C为例int n, m; // 顶点数边数 cin n m; vectorvectorint adj(n); // 邻接表存储邻居顶点 // 或者对于带权图 // vectorvectorpairint, int adj(n); // pair邻居, 边权 for (int i 0; i m; i) { int u, v; cin u v; // 假设输入顶点从1开始编号 u--; v--; adj[u].push_back(v); adj[v].push_back(u); // 如果是无向图切记要加这一行 }这种实现兼具了空间效率和缓存友好性。4.3 性能的量化对比与一个关键误区我们来做一个简单的量化对比。假设有一个图n10000个顶点m20000条边这是一个稀疏图。空间邻接矩阵需要10000 * 10000 100,000,000个int。按4字节算约381 MB。邻接表存储20000 * 2 40000条边信息无向图每条边存两次加上顶点数组开销大约在0.3 MB量级。相差超过1000倍时间查询边(u,v)是否存在矩阵O(1)一次访问。邻接表O(degree(u))。如果u是一个平均顶点degree约等于4那么平均需要查找2次。但如果需要频繁查询这个开销累积起来可能很大。遍历顶点v的所有邻居矩阵O(n)需要检查10000个元素。邻接表O(degree(v))平均只需检查4个元素。一个关键误区邻接表一定比矩阵快吗不一定。对于“遍历所有边”这个操作邻接矩阵需要两层循环遍历整个矩阵复杂度 O(n²)。邻接表需要遍历所有顶点的邻居列表复杂度 O(n m)。在稀疏图下O(nm) 远小于 O(n²)。 但是如果图非常稠密m 接近 n²那么 O(nm) 就约等于 O(n²)两者时间复杂度相当。而此时邻接矩阵连续的内存访问模式可能比邻接表分散的访问带来更好的缓存性能实际运行速度可能更快。所以“快慢”必须结合具体操作和图的结构来分析。5. 从存储到应用以路径搜索为例看底层影响为了让你更直观地理解存储选择如何影响上层应用我们以最常见的图算法——广度优先搜索BFS为例看看不同存储下的实现差异和性能表现。5.1 基于邻接矩阵的BFS实现使用邻接矩阵时BFS的核心循环中探索一个顶点u的所有邻居需要遍历matrix[u]的整行。void bfs_matrix(int start, vectorvectorint matrix) { int n matrix.size(); vectorbool visited(n, false); queueint q; visited[start] true; q.push(start); while (!q.empty()) { int u q.front(); q.pop(); // 遍历所有顶点检查是否为邻居 for (int v 0; v n; v) { if (matrix[u][v] 1 !visited[v]) { visited[v] true; q.push(v); } } } }问题显而易见即使顶点u只有一个邻居这个for循环也要跑完n次迭代。在稀疏图下这造成了巨大的计算浪费。整个BFS的时间复杂度为 O(n²)。5.2 基于邻接表的BFS实现使用邻接表时我们可以直接遍历adj[u]这个列表里面全是真正的邻居。void bfs_adjlist(int start, vectorvectorint adj) { int n adj.size(); vectorbool visited(n, false); 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); } } } }这里for (int v : adj[u])的迭代次数就是顶点u的度数。整个BFS会访问每个顶点一次并检查每条边两次无向图因此时间复杂度是 O(n m)。对于稀疏图这比 O(n²) 快得多。5.3 性能实测的启示我曾经在一个有5000个顶点、约2万条边的社交网络子图上测试过两种实现的BFS。邻接表版本完成全图遍历耗时约15毫秒而邻接矩阵版本耗时超过了800毫秒。差距高达50倍以上这个例子生动地说明在错误的场景下使用邻接矩阵性能惩罚是灾难性的。实操心得在实现图算法时优先使用邻接表。除非有非常确凿的理由如顶点数极少、需要O(1)的边查询、或进行矩阵运算否则邻接表都是更安全、更高效的选择。在LeetCode等平台刷题时这也是一条黄金法则。养成习惯看到图问题首先想到vectorvectorint adj。6. 进阶话题存储形式的变体与工程实践在实际的系统和高级图算法中基础的邻接矩阵和邻接表可能会进行优化或变形以适应更特殊的需求。6.1 邻接矩阵的优化稀疏矩阵存储对于规模很大但仍是稀疏的图如果因为算法原因必须使用矩阵表示比如某些线性代数运算直接使用二维数组是不可行的。这时会采用稀疏矩阵的存储格式如CSRCompressed Sparse Row或CSCCompressed Sparse Column。以CSR为例它用三个数组来存储矩阵values: 存储所有非零元素的值。col_indices: 存储每个非零元素所在的列索引。row_ptr: 存储每一行第一个非零元素在values中的起始位置。这本质上是对邻接表思想的一种矩阵化表述兼具了矩阵的运算特性和稀疏存储的高效性。许多科学计算库如SciPy和图神经网络框架在处理大规模图时底层都是用CSR格式存储邻接关系的。6.2 邻接表的优化针对特定操作的调整基础的邻接表也有可以优化的地方频繁边查询如果应用需要频繁判断(u, v)边是否存在可以在每个顶点的邻居列表外再维护一个哈希集合如unordered_set。这样添加/删除边是 O(1) 均摊时间查询也是 O(1)。当然这增加了空间开销和实现的复杂度。带权图的存储前面提到用vectorvectorpairint, int其中pair的第一个元素是邻居顶点第二个是边权。这是最通用的做法。如果边权类型固定且需要极致性能可以考虑用结构体数组。动态图的极致优化对于边变化极其频繁的图链表版本的邻接表在中间插入/删除时可能更有优势。但考虑到缓存问题通常需要实现一个内存池来分配链表节点以减少内存碎片。6.3 如何根据“热词”中的场景选择回顾我们开头看到的一些网络热词它们背后对应着不同的图存储需求图神经网络、因子图优化这些领域通常处理的是规模中等的图并且计算涉及矩阵乘法或消息传递。通常采用稀疏矩阵格式如CSR或邻接表作为输入。框架会帮你处理好存储但理解底层是邻接表的思想很重要。ROS SLAM建图、遥感卫星图识别这类问题中的图通常是位姿图或特征点图顶点和边的数量可能很大且是稀疏的。邻接表是更自然的选择便于进行图优化迭代。图数据库如Neo4j图数据库的核心是高效存储和查询关联关系。它们使用的存储引擎极其复杂但思想上是邻接表的超集会结合B树、跳表、压缩等技术来优化不同方向的遍历查询。思维导图、UML类图、流程图这些是图的视觉化应用。编辑时顶点和边的数量通常不多几百个以内且需要频繁查询和更新连接关系。在内存中使用邻接矩阵或优化的邻接表带哈希查询都可以关键是要与渲染引擎高效配合。7. 总结与最终建议没有银弹只有权衡聊了这么多我们可以下一个结论了邻接矩阵和邻接表没有绝对的好坏只有适合与不适合。当你需要做出选择时可以遵循这个决策流程评估图的规模与密度顶点数n和边数m是多少计算一下m和n²的关系。如果m接近n²稠密图考虑矩阵如果m远小于n²稀疏图坚决用邻接表。明确核心操作你的算法最频繁的操作是什么如果是“给定两个顶点查是否存在边”且此操作频率极高稠密图下矩阵有优势。如果是“遍历一个顶点的所有邻居”BFS/DFS/最短路径或“遍历所有边”邻接表几乎总是更好的选择。考虑动态性图的结构是静态的还是动态变化的频繁增删顶点邻接表更灵活。利用现有框架如果你在使用某个图算法库或机器学习框架先去了解它推荐或内置的存储格式。不要重复造轮子。从我个人的经验来看在超过九成的实际开发和学习场景中邻接表特别是用动态数组实现的版本都是那个更安全、更通用的起点。它平衡了空间、时间和实现的复杂度。邻接矩阵则像一把特种手术刀在顶点数少、图稠密、需要快速随机访问边的特定场景下它能发挥出简洁高效的优势。最后记住一点理解数据结构的本质比死记硬背它的优缺点更重要。理解了“矩阵用空间换时间记录所有可能链表用时间换空间只记录实际存在”你就能在面对任何新问题时灵活地做出最适合的存储设计。