当前位置：首页 > news >正文

邻接矩阵与邻接表：图数据结构选型与性能权衡指南

news 2026/8/7 13:56:59

1. 从“图”说起：为什么我们需要邻接矩阵和邻接表？

如果你写过代码，处理过社交网络的好友关系、地图导航的路径规划，或者仅仅是配置过一些复杂的软件依赖，那么你其实已经在和“图”打交道了。图，这个听起来有点学术的词，本质上就是一种描述“事物之间关系”的模型。点代表事物，线代表关系。今天我们不聊那些花哨的图神经网络或者复杂的算法，就聊聊最基础、也最要命的一件事：在计算机里，我们到底该怎么把一张“图”给存起来？

你可能会想，这还不简单？画出来不就行了。但计算机不认识你画的圈圈和线，它只认识0和1，只认识数组和指针。所以，我们需要一种“表示方式”，把图上点和线的关系，翻译成计算机能理解和高效处理的数据结构。这就引出了我们今天要掰扯清楚的两个核心方法：邻接矩阵和邻接表。它们俩就像工具箱里的锤子和螺丝刀，各有各的用武之地，用错了地方，要么事倍功半，要么直接“砸了脚”。

我见过不少新手，一上来就死记硬背“稠密图用矩阵，稀疏图用表”，但真到写代码的时候还是懵的。为什么？因为没搞懂这两种结构到底是怎么在内存里“摆开阵势”的，更没明白不同的“摆法”会如何深刻影响你后续每一个操作——查找一个点的邻居、遍历整张图、计算连通性——的效率。这篇文章，我就结合我这些年掉过的坑和总结的经验，带你从内存布局的视角，彻底搞懂有向图和无向图在这两种表示法下的细微差别，让你下次面对图相关的问题时，能毫不犹豫地选出最趁手的那把“工具”。

2. 邻接矩阵：用“表格”来刻画关系

邻接矩阵是最直观，也最“暴力”的一种表示方法。它的核心思想非常简单：如果一张图有n个顶点，我就用一个n x n的二维数组（矩阵）matrix来表示它。数组的行和列都对应着图的顶点。

2.1 基本规则与内存布局

这个矩阵里的每一个元素matrix[i][j]都代表了一条从顶点i到顶点j的边。它的取值决定了边的属性：

无权图：通常用0或1表示。1表示存在从i到j的边，0表示不存在。
有权图：matrix[i][j]存储的就是这条边的权重（如距离、成本）。可以用一个特殊值（如INF无穷大）来表示不存在边。

对于无向图而言，如果顶点A和B之间有一条边，那么这条边是双向的、没有方向的。反映到邻接矩阵上，就意味着matrix[A][B]和matrix[B][A]这两个位置的值应该相同（都是1，或者都是相同的权重）。因此，无向图的邻接矩阵一定是一个对称矩阵。你只需要看矩阵的上三角（或下三角）部分，就能知道所有的边。

对于有向图，边的方向至关重要。matrix[A][B] = 1只表示有一条从A指向B的弧，而matrix[B][A]的值则独立，可能为0也可能为1。所以，有向图的邻接矩阵通常不对称。

让我们来看一个具体的例子。假设我们有一个包含4个顶点（0， 1， 2， 3）的无向图，边的情况如下： (0-1)， (0-2)， (1-2)， (2-3)。它的邻接矩阵会是：

0 1 2 3 0 [0, 1, 1, 0] 1 [1, 0, 1, 0] 2 [1, 1, 0, 1] 3 [0, 0, 1, 0]

你可以看到matrix[0][1] = 1且matrix[1][0] = 1，体现了无向边的对称性。

在内存中，这个n x n的矩阵会被分配一块连续的空间。例如在C/C++中，它可能是一个静态的二维数组，也可能是一个动态分配的、扁平化的一维数组（通过matrix[i*n + j]来访问(i, j)）。无论哪种，它都清晰地占据着O(n^2)的空间。

2.2 优势与代价：为什么说它“简单粗暴”？

邻接矩阵的优势极其明显，这也是它为什么常被初学者首先想到的原因：

查询速度极快：判断任意两个顶点u和v之间是否存在边，或者获取边的权重，时间复杂度是O(1)。直接数组索引matrix[u][v]即可，这是任何其他方法都无法比拟的。
对稠密图友好：当图的边数量接近顶点数量的平方（即e ≈ n^2）时，矩阵的空间利用率很高，几乎每个格子都被用上了。
结构直观清晰：矩阵本身就是一个完整的关系表，对于一些小规模图，直接打印出来就能一目了然地看清全局拓扑。

但是，它的代价也同样“粗暴”：

空间复杂度高：无论图里有多少条边，只要顶点数n定了，空间开销就是O(n^2)。这对于顶点很多但边很稀疏的图（比如社交网络，每个人认识的人有限）来说是巨大的浪费。一个1万个顶点的图，矩阵就要1亿个存储单元，大部分都是0。
添加/删除顶点成本高：增加一个顶点意味着需要重新分配一个(n+1) x (n+1)的矩阵并拷贝数据，成本是O(n^2)。这在图动态变化的场景中很致命。
遍历邻居效率低：要找出顶点v的所有邻居，你需要扫描矩阵的第v行（或第v列）的全部n个元素，即使它只有两三个邻居。时间复杂度是O(n)，在稀疏图中这非常低效。

实操心得：邻接矩阵就像一张巨大的、画满了所有可能关系的网格纸。当关系真的非常密集时，它物尽其用；但当关系稀疏时，这张纸上就布满了无意义的空白。在算法竞赛中，如果题目明确顶点数n <= 500或1000，且图比较稠密，用矩阵代码写起来会非常快。但在工程中，面对动辄百万顶点的大型网络，几乎不会直接使用朴素的邻接矩阵。

3. 邻接表：用“链表”来记录关联

为了解决邻接矩阵在稀疏图上的空间浪费问题，邻接表应运而生。它的核心思想从“记录所有可能关系”转变为“只记录实际存在的关系”。

3.1 核心思想与结构剖析

邻接表的结构可以类比成一种“通讯录”。对于图中的每一个顶点v，我们都维护一个列表（可以是数组、链表、集合等），这个列表里存放着所有与v直接相连的邻居顶点信息。

对于无向图：如果顶点A和B之间有一条边，那么B会出现在A的邻居列表里，同时A也会出现在B的邻居列表里。每条边在数据结构中被存储了两次。
对于有向图：如果有一条从A指向B的边，那么B只会出现在A的出边邻居列表里。如果你想快速找到所有指向B的边（入边），可能需要额外维护一个“逆邻接表”。

常见的实现方式是用一个数组（或字典）adj，其中adj[v]对应顶点v的邻居列表。这个列表本身可以用多种数据结构实现：

动态数组（Vector/ArrayList）：最常用。内存连续，缓存友好，遍历快。
链表：频繁增删边时效率高，但遍历和随机访问慢。
哈希集合（HashSet）：需要快速判断某个特定邻居是否存在时使用，但存储开销稍大。

还是用刚才那个4顶点的无向图例子，它的邻接表（用动态数组实现）看起来是这样的：

顶点0: [1, 2] 顶点1: [0, 2] 顶点2: [0, 1, 3] 顶点3: [2]

一目了然，每个顶点只关心自己的“朋友圈”。

3.2 优势与适用场景分析

邻接表的优势恰恰弥补了矩阵的劣势：

空间效率高：存储空间与图中的实际边数e和顶点数n成正比。对于稀疏图，空间复杂度约为O(n + e)，远小于O(n^2)。
遍历邻居高效：要找出顶点v的所有邻居，只需要遍历adj[v]这个列表，时间复杂度是O(degree(v))，其中degree(v)是顶点v的度（邻居数）。在稀疏图中，这比矩阵的O(n)快得多。
动态增删边方便：在邻居列表中添加或删除一个元素，通常成本很低（数组尾部添加O(1)，链表O(1)，哈希集O(1)平均）。添加顶点也只需在adj数组末尾追加一个空列表。

当然，它也有自己的短板：

查询边存在性慢：判断顶点u和v之间是否有边，需要遍历adj[u]列表（或者adj[v]），时间复杂度是O(degree(u))，最坏情况是O(n)。虽然可以用哈希集合优化到平均O(1)，但增加了复杂度。
对稠密图不友好：当边数非常多时，邻接表存储每条边两次（无向图）以及维护多个列表指针的开销，可能并不比矩阵节省太多空间，反而失去了矩阵的随机访问优势。
实现稍复杂：相比矩阵的简单二维数组，邻接表需要管理多个动态集合，代码实现上更复杂一些。

实操心得：邻接表是绝大多数图算法实际应用的默认选择，尤其是在处理社交网络、网页链接、交通网络等天然稀疏的大规模图时。在C++中，我强烈推荐使用vector<vector<int>>或vector<vector<pair<int, int>>>（对于有权图）来实现，它在空间局部性和访问效率上取得了很好的平衡。在Python中，用列表的列表（List[List[int]]）或字典（defaultdict(list)）也非常方便。

4. 有向图与无向图在表示上的关键差异

理解了两种基本结构后，我们需要更细致地审视有向图和无向图在实现时带来的不同。这不仅仅是“对称与否”的问题，它影响着我们如何初始化、如何添加边以及如何设计算法。

4.1 无向图的“双向”承诺

对于无向图，我们必须牢记：一条无向边等于两条方向相反的有向边。这个承诺必须在数据结构层面兑现。

在邻接矩阵中：添加边(u, v)时，必须同时设置matrix[u][v] = 1和matrix[v][u] = 1。初始化时，矩阵自然就是对称的。很多基于矩阵的算法（如计算度数）可以利用这个对称性进行优化，只遍历一半矩阵。
在邻接表中：添加边(u, v)时，必须执行adj[u].push_back(v)和adj[v].push_back(u)。这意味着每条边在存储中被记录了两次。因此，当你需要计算图中总边数时，不能简单地将所有adj[v].size()相加，因为这样会重复计算。正确做法是加总后除以2，或者在添加边时用一个计数器单独维护。

一个常见的坑是忘记这个“双向”操作，导致图变成“半身不遂”，遍历时只能走单向，连通性判断完全错误。我在早期写代码时就没少犯这个错误，调试了半天才发现是因为addEdge函数只做了一次插入。

4.2 有向图的“方向”语义

有向图的边具有明确的从“源点”（尾）到“目标点”（头）的方向。这带来了更丰富的关系，但也需要更仔细地处理。

在邻接矩阵中：边(u, v)仅表示从u到v，所以只设置matrix[u][v] = 1。matrix[v][u]代表的是反向边，独立存在。矩阵通常不对称。
在邻接表中：这是最自然的方式。adj[u]这个列表存储的是从顶点u出发能直接到达的所有顶点（即u的出边邻居）。这个列表清晰地刻画了顶点的“影响力”或“辐射范围”。

有向图引入了一个关键概念：入度和出度。

出度：从顶点v出发的边的数量，在邻接表中就是adj[v].size()。
入度：指向顶点v的边的数量。这在邻接表中无法直接快速获得！你需要遍历所有顶点的邻居列表，统计v出现的次数，成本是O(n+e)。

如果需要频繁查询入度（例如在拓扑排序、计算网页的PageRank时），有两种策略：

维护一个“逆邻接表”：另一个数组radj，其中radj[v]存储所有指向v的顶点。这样入度查询和遍历入边邻居都是O(degree_in(v))。代价是空间翻倍，且增删边需要同步更新两个表。
单独维护一个入度数组：在初始化建图时，就计算并维护一个inDegree[v]数组。添加边(u, v)时，执行inDegree[v]++。这样查询入度是O(1)，但无法快速获取具体的入边邻居列表。

选择哪种策略，完全取决于你的算法需要什么。例如做拓扑排序（Kahn算法），只需要入度值而不需要具体的入边列表，那么维护一个inDegree数组就是最经济高效的选择。

5. 实战场景与数据结构选型指南

理论说再多，不如看实战。我们结合几个典型的场景和从热搜词里看到的实际问题，来分析如何选择。

5.1 场景一：小规模稠密图与算法竞赛

典型场景：算法题中顶点数n <= 500的图论题；需要频繁判断任意两点间是否有边；图本身比较稠密（比如完全图、网格图）。

选型与理由：邻接矩阵是首选。

理由1：编码速度极快。用一个二维数组，所有操作都简化为数组赋值和访问，不容易出错。
理由2：O(1)的边查询。很多基于动态规划的图算法（如Floyd-Warshall全源最短路径）需要频繁读取任意两点间的距离，矩阵的随机访问优势无可替代。
理由3：空间可以接受。500x500的矩阵，在大多数语言中只占约1MB（假设int类型）的内存，完全在限制内。

实现注意点：对于有权图，记得用INF（一个很大的数，如0x3f3f3f3f）初始化矩阵来表示“无边”。对于无向图，添加边务必设置对称的两个位置。

5.2 场景二：大规模稀疏网络与工程系统

典型场景：社交网络分析（用户作为顶点，关注关系作为边）；网页爬虫（URL作为顶点，超链接作为有向边）；推荐系统（用户-物品二分图）；知识图谱。

选型与理由：邻接表是绝对的主流。

理由1：内存是硬约束。百万顶点、千万边的图，矩阵需要TB级别内存，而邻接表可能只需要GB级别。
理由2：遍历操作是核心。诸如广度优先搜索（BFS）、深度优先搜索（DFS）、Dijkstra最短路径等算法，核心操作是遍历顶点的邻居。邻接表的O(degree)效率远高于矩阵的O(n)。
理由3：易于扩展。动态添加新顶点或新边非常自然。

进阶技巧：

使用vector<vector<pair<int, int>>>存储带权图，pair中第一个元素是邻居顶点，第二个是权重。
如果需要去重边（例如多次添加同一条边），可以考虑用vector<unordered_set<int>>，但会牺牲一些遍历的缓存性能。
对于超大规模图，可能需要使用压缩稀疏行（CSR）格式，这是一种将邻接表扁平化存储的工业级格式，能进一步压缩空间并提升缓存命中率。

5.3 场景三：需要快速查询入度的有向图处理

典型场景：任务调度（拓扑排序）；计算有向图中顶点的PageRank或影响力；分析数据流或依赖关系。

选型与理由：邻接表（出边表） + 入度数组。

理由：拓扑排序的Kahn算法核心就是不断移除入度为0的顶点。我们既需要快速遍历一个顶点的所有出边（邻接表擅长），又需要快速获取和修改任意顶点的入度（入度数组擅长）。维护一个单独的inDegree数组，空间开销仅为O(n)，是性价比最高的方案。

操作示例：

// 假设有n个顶点，边列表为vector<pair<int, int>> edges vector<vector<int>> adj(n); // 邻接表 vector<int> inDegree(n, 0); // 入度数组 for (auto& [u, v] : edges) { adj[u].push_back(v); // 添加出边 inDegree[v]++; // 更新入度 }

这样，在拓扑排序中，我们可以快速找到所有inDegree[i] == 0的顶点加入队列。

5.4 场景四：频繁的边存在性检查

典型场景：某些图算法中需要反复判断某条边是否存在；在构建图的过程中需要避免添加重复边。

选型与理由：根据图密度决定。

如果是稠密图：坚持使用邻接矩阵，O(1)的查询无可匹敌。
如果是稀疏图，但查询极其频繁：可以考虑使用邻接表，但内部用哈希集合（如unordered_set）代替列表或数组。这样添加边和查询边是否存在都可以在平均O(1)时间内完成。代价是哈希表本身的开销和遍历时稍慢的缓存性能。
折中方案：对于一般的稀疏图，如果只是偶尔查询，遍历邻居列表O(degree)也是可以接受的。毕竟在稀疏图中，degree通常很小。

6. 从表示到算法：深度优先搜索（DFS）的实现差异

我们以热搜词中的“无向图深度优先搜索”为例，看看不同的图表示方法如何影响一个具体算法的实现。DFS的核心在于“不撞南墙不回头”的递归探索，需要标记已访问顶点，并递归访问当前顶点的所有未访问邻居。

6.1 基于邻接矩阵的DFS实现

用矩阵实现时，寻找一个顶点的所有邻居，需要扫描它对应的整行（或整列）。

void dfs_matrix(int v, vector<vector<int>>& matrix, vector<bool>& visited) { visited[v] = true; // 处理顶点 v cout << v << " "; int n = matrix.size(); // 关键：遍历所有顶点，检查是否为邻居 for (int i = 0; i < n; i++) { // 如果 matrix[v][i] 为真（且i未被访问），则i是v的邻居 if (matrix[v][i] && !visited[i]) { dfs_matrix(i, matrix, visited); } } }

特点分析：无论顶点v有多少个实际邻居，这个循环都要跑满n次。在稀疏图中，这做了大量无用的matrix[v][i]检查（检查值是否为0）。算法的时间复杂度为O(n^2)，因为每个顶点都要扫描一行（n次），总共有n个顶点。这在稀疏图上是非常低效的。

6.2 基于邻接表的DFS实现

用邻接表实现时，我们可以直接遍历adj[v]这个精确的邻居列表。

void dfs_list(int v, vector<vector<int>>& adj, vector<bool>& visited) { visited[v] = true; // 处理顶点 v cout << v << " "; // 关键：直接遍历v的邻居列表 for (int neighbor : adj[v]) { if (!visited[neighbor]) { dfs_list(neighbor, adj, visited); } } }

特点分析：循环次数等于顶点v的实际度数degree(v)。对于整个图的DFS，每个顶点被访问一次，每条边（在邻接表中存储了两次）会在端点处各被遍历一次。因此，总的时间复杂度是O(n + 2e) = O(n + e)。在稀疏图（e远小于n^2）中，这比矩阵的实现快得多。

这个对比清晰地展示了数据结构选择对算法性能的直接影响。邻接表让算法只关注“存在”的关系，避免了在“空白”上的无效操作。

7. 总结与个人经验谈

聊了这么多，最后再分享几个我踩过坑才记住的经验点：

无向图加边要加两次：这看似简单，却是最容易忘记的bug来源。写一个addEdge(u, v, isDirected=false)的辅助函数是个好习惯。
邻接表初始化别忘了：使用vector<vector<int>> adj(n)后，adj里已经有n个空的vector了。但如果用vector<int> adj[n]（C风格数组）或List<List<Integer>> adj = new ArrayList<>(n)（Java），记得要为每个位置初始化一个新的空列表对象，否则会导致空指针异常。
根据操作频率选型：不要死记“稀疏用表，稠密用阵”。问问自己：我的核心操作是什么？是遍历邻居（选表），还是随机查边（选阵或哈希表），亦或是查入度（可能需要额外数组）？分析清楚操作模式，选择才能最优。
空间与时间的权衡：邻接表省空间，但牺牲了常数时间的查边。邻接矩阵查边快，但浪费空间。在内存充裕的小规模问题中，矩阵的简单性是巨大优势；在大数据场景下，表的空间效率是生存之本。有时候，为了特定操作（如快速查边），在邻接表里套一个哈希集合，是一种用空间换时间的实用折中。
测试时从简单图开始：调试图算法时，先用一个3-5个顶点的小图，手工画出它的矩阵和邻接表表示，然后单步跟踪你的代码，看数据结构的构建和算法的每一步是否符合预期。这比直接在大图上抓瞎要高效得多。