1. 从一次内存告警说起为什么邻接矩阵会“撑爆”你的程序很多同学第一次接触图论都是从邻接矩阵开始的。原因很简单它太符合直觉了——一个二维数组matrix[i][j]值为1就表示从顶点 i 到顶点 j 有一条边值为0就表示没有。写起来快理解起来也快考试画图更是方便。但如果你真的拿它去跑一个稍微大一点的真实数据比如几万个顶点、几十万条边的社交网络关系图程序大概率会在某个时刻直接崩掉或者被操作系统的内存告警打断。我印象很深的一次经历是帮一个做数据分析的朋友排查一个脚本崩溃的问题。他的需求很简单读入一份大约五万个节点的关系数据然后判断任意两个节点之间是否存在直接连接。他用了邻接矩阵开了一个50000 x 50000的二维数组。我们算一下如果每个元素用1个字节的布尔值来存那就是 50000 × 50000 25亿字节也就是大约 2.5 GB。这还只是最理想的情况实际在多数编程语言里布尔值往往占1个字节甚至更多而如果用整型来存那就是 10 GB 起步。普通开发机的内存根本扛不住更别提还要在这个矩阵上做遍历和查询了。这就是邻接矩阵最致命的短板空间复杂度是 O(V²)其中 V 是顶点数量。它只和顶点数有关和你实际有多少条边完全无关。一个五万节点的图哪怕只有五万条边平均每个节点只连一条边它也要吃掉 2.5 GB 的内存。而现实中的图绝大多数都是稀疏图——边数 E 远远小于 V²。比如社交网络里一个用户平均可能只有几百个好友而不是几万个。所以理解邻接矩阵和邻接表这两种存储结构绝不只是背两个定义、应付一道考试题。它直接决定了你写的图算法能不能在真实数据上跑起来决定了你的程序是几毫秒出结果还是直接内存溢出。这篇文章我就把这两种结构从底层原理、代码实现、适用场景到实际踩坑完整地拆一遍。无论你是正在准备数据结构课程的学生还是工作中需要处理图数据的开发者都能从中找到可以直接复用的东西。2. 邻接矩阵的底层逻辑与代码落地2.1 矩阵存储的核心思想用空间换时间邻接矩阵的本质是用一个二维数组来记录任意两个顶点之间的连接关系。假设图有 n 个顶点编号从 0 到 n-1那么我们就开一个n x n的数组adj。对于无权图adj[i][j] 1表示顶点 i 到顶点 j 有边 0表示没有。对于带权图adj[i][j]直接存这条边的权重用一个特殊值比如无穷大表示没有边。这种设计带来的最大好处是查询效率极高。判断两个顶点之间是否有边只需要一次数组下标访问时间复杂度是 O(1)。这在某些需要频繁做边存在性判断的算法里非常关键。比如在 Floyd-Warshall 算法求所有点对最短路径时邻接矩阵就是最自然的存储方式因为算法本身就要反复访问dist[i][j]。但代价也很明显。首先是空间O(V²) 的复杂度意味着顶点数稍微上去一点内存就爆炸。其次是遍历某个顶点的所有邻居时即使这个顶点只有一条边你也必须扫描整行 n 个元素时间复杂度是 O(V)。对于稀疏图来说这是巨大的浪费。还有一个容易被忽略的点无向图的邻接矩阵是对称的。也就是说adj[i][j] adj[j][i]。这意味着你实际上存了两份完全相同的信息空间利用率只有一半。有经验的开发者会利用对称性做压缩存储比如只存上三角或下三角把空间省下来一半。不过这样会让下标计算变复杂需要权衡。2.2 用二维数组实现邻接矩阵下面用 Python 写一个最基础的邻接矩阵实现。选择 Python 是因为它足够直观方便理解逻辑实际工程中如果追求性能可以用 C 或 Java 的数组。class GraphMatrix: def __init__(self, num_vertices, directedFalse): self.num_vertices num_vertices self.directed directed # 初始化 n x n 矩阵全部填 0 self.matrix [[0] * num_vertices for _ in range(num_vertices)] def add_edge(self, u, v, weight1): self.matrix[u][v] weight # 如果是无向图对称位置也要赋值 if not self.directed: self.matrix[v][u] weight def has_edge(self, u, v): return self.matrix[u][v] ! 0 def get_neighbors(self, u): neighbors [] for v in range(self.num_vertices): if self.matrix[u][v] ! 0: neighbors.append((v, self.matrix[u][v])) return neighbors这段代码里有一个细节值得说初始化矩阵时用了[[0] * n for _ in range(n)]而不是[[0] * n] * n。后者是 Python 新手常踩的坑它创建的是 n 个指向同一个列表的引用修改任意一行会同时影响所有行。这个坑在实现邻接矩阵时特别容易遇到因为矩阵的每一行看起来“应该”是独立的。add_edge方法里对无向图的处理也很关键。无向图的一条边 (u, v) 在矩阵里要写两个位置matrix[u][v]和matrix[v][u]。如果漏了对称赋值后续遍历邻居时就会漏掉一半的边导致算法结果完全错误。这种 bug 很隐蔽因为图看起来“能跑”只是结果不对。2.3 邻接矩阵的适用边界与性能实测那到底什么时候该用邻接矩阵我的经验是看两个指标顶点规模和图的稠密程度。如果顶点数在几百到一两千以内邻接矩阵完全没问题。比如一个一千节点的图矩阵占 100万 个元素用整型存也就 4 MB现代机器毫无压力。而且这个规模下O(1) 的边查询和简单的代码逻辑能帮你省下大量调试时间。但如果顶点数上万就要慎重了。我做过一个简单的实测在同样的机器上用 Python 构建一个一万节点的图邻接矩阵初始化就要分配一亿个元素耗时大约 1.5 秒内存占用接近 800 MBPython 的 int 对象开销大。而同样一万节点、五万条边的稀疏图用邻接表构建只需要几十毫秒内存占用不到 10 MB。差距是数量级的。还有一个场景要特别注意动态图。如果你的图需要频繁地增加或删除顶点邻接矩阵会非常痛苦因为每次增加顶点都要重新分配整个矩阵并复制数据。而邻接表增加一个顶点只是加一个空列表成本极低。所以我的建议是邻接矩阵适合顶点数少、边密集、且需要频繁查询任意两点间关系的场景。比如小规模的网络流问题、状态转移图、或者教学演示。一旦顶点规模上去或者图明显稀疏就应该果断换邻接表。3. 邻接表稀疏图场景下的主力方案3.1 邻接表的存储结构拆解邻接表的思路和邻接矩阵完全不同。它不再关心“任意两点之间有没有边”而是只记录“每个顶点到底连了哪些顶点”。具体来说就是为每个顶点维护一个列表或链表列表里存的是这个顶点的所有邻居。用生活化的类比邻接矩阵像一张巨大的通讯录表格行和列都是所有人交叉格子记录两人是否认识。哪怕你只认识三个人表格里也要为所有其他人留出空格。而邻接表像每个人的手机通讯录只存自己真正认识的人没存的就是不认识。显然在大多数人只认识少数人的情况下通讯录的方式高效得多。邻接表的空间复杂度是O(V E)只和顶点数和边数有关。对于稀疏图E 远小于 V²所以空间占用远低于邻接矩阵。遍历某个顶点的所有邻居时也只需要遍历它自己的列表时间复杂度是 O(degree)degree 是该顶点的度数而不是 O(V)。这在稀疏图里是巨大的性能优势。但邻接表也有代价。判断两个顶点 u 和 v 之间是否有边需要遍历 u 的邻居列表最坏情况下时间复杂度是 O(degree)而不是 O(1)。如果算法需要频繁做这种判断邻接表就会成为瓶颈。3.2 三种主流实现方式对比邻接表在具体实现上有几种常见变体各有取舍。第一种是列表的列表也就是用一个数组每个元素是一个列表。这是最直观的实现Python 里就是adj [[] for _ in range(n)]。添加边就是adj[u].append(v)。优点是代码简单遍历方便。缺点是删除边时需要遍历列表找到并移除效率较低。第二种是字典的列表每个顶点的邻居存成字典键是邻居编号值是权重。这样查询某条边是否存在可以做到 O(1)同时保留了邻接表的空间优势。适合带权图且需要频繁查询边权重的场景。第三种是链式前向星用数组模拟链表在 C 竞赛圈非常流行。它用head数组记录每个顶点的第一条边用next数组把同一起点的边串起来。优点是内存紧凑、缓存友好、遍历快缺点是代码不够直观调试麻烦。实现方式空间开销边查询添加边删除边适用场景列表的列表低O(degree)O(1)O(degree)通用遍历为主字典的列表中O(1)O(1)O(1)带权图频繁查边链式前向星最低O(degree)O(1)困难竞赛性能敏感选择哪种取决于你的核心操作是什么。如果主要是遍历邻居做 BFS 或 DFS列表的列表就够了。如果需要频繁判断边是否存在字典的列表更合适。如果是在性能极限的竞赛环境链式前向星是首选。3.3 邻接表的完整代码实现下面给出一个基于字典的邻接表实现兼顾了空间效率和边查询效率。class GraphAdjList: def __init__(self, directedFalse): self.directed directed # 外层字典顶点 - 邻居字典 self.adj {} def add_vertex(self, v): if v not in self.adj: self.adj[v] {} def add_edge(self, u, v, weight1): self.add_vertex(u) self.add_vertex(v) self.adj[u][v] weight if not self.directed: self.adj[v][u] weight def has_edge(self, u, v): return u in self.adj and v in self.adj[u] def get_neighbors(self, u): return list(self.adj.get(u, {}).items()) def remove_edge(self, u, v): if self.has_edge(u, v): del self.adj[u][v] if not self.directed: del self.adj[v][u]这个实现用字典而不是列表来存邻居好处是顶点编号不需要是连续的整数可以是任意可哈希的对象比如字符串。这在处理真实数据时非常实用因为节点 ID 往往是字符串或者不连续的整数。add_vertex方法保证了即使先添加边再添加顶点或者顶点是孤立点结构也不会出错。remove_edge同时处理了有向图和无向图的情况无向图要删两个方向。有一个细节要注意get_neighbors返回的是list(...)把字典的视图转成了列表。这样做是为了避免调用者在遍历时修改字典导致运行时错误。如果追求极致性能可以不转列表但要提醒调用者不要边遍历边修改。4. 两种结构的转换与选型决策4.1 从矩阵到表、从表到矩阵的转换实际工作中经常遇到需要在这两种结构之间转换的情况。比如数据源给的是邻接矩阵格式但你的算法需要邻接表或者你算完邻接表需要输出成矩阵格式给下游系统。从邻接矩阵转邻接表逻辑很直接遍历矩阵的每一行对于matrix[i][j] ! 0的位置在邻接表里给顶点 i 添加邻居 j。def matrix_to_adjlist(matrix): n len(matrix) adj [[] for _ in range(n)] for i in range(n): for j in range(n): if matrix[i][j] ! 0: adj[i].append((j, matrix[i][j])) return adj从邻接表转邻接矩阵需要先知道顶点总数然后开一个 n x n 的矩阵遍历每个顶点的邻居列表填充。def adjlist_to_matrix(adj, n): matrix [[0] * n for _ in range(n)] for u in range(n): for v, w in adj[u]: matrix[u][v] w return matrix转换本身不复杂但要注意有向图和无向图的区别。如果原图是无向图转换后矩阵应该是对称的。如果转换代码只填了一个方向就会丢失信息。我在实际项目里见过因为转换时漏了对称赋值导致后续算法把无向图当成有向图处理结果完全错误的情况。另外转换的代价要心里有数。矩阵转表是 O(V²)因为要扫描整个矩阵。表转矩阵是 O(V E)因为只遍历实际存在的边。如果数据量大转换本身可能成为性能瓶颈能避免就避免尽量让数据从一开始就以目标格式存在。4.2 选型决策树到底该用哪个说了这么多实际做选择时可以按下面这个思路走。第一步看顶点规模。如果顶点数超过一万基本可以排除邻接矩阵除非你确认内存绝对充足且图非常稠密。如果顶点数在几千以内两者都可以考虑。第二步看图的稠密程度。计算一下边数 E 和 V² 的比值。如果 E 接近 V²说明是稠密图邻接矩阵的空间劣势不再明显而它的查询优势可以发挥。如果 E 远小于 V²比如 E V × log(V)那就是稀疏图邻接表是更好的选择。第三步看核心操作。如果算法需要频繁判断任意两点间是否有边比如 Floyd 算法、传递闭包计算邻接矩阵更合适。如果主要是遍历邻居比如 BFS、DFS、拓扑排序邻接表更合适。第四步看图是否动态变化。频繁增删顶点选邻接表。图一旦建好就不变两者都行。判断维度倾向邻接矩阵倾向邻接表顶点规模小 几千大 一万稠密程度稠密图稀疏图核心操作频繁查边遍历邻居动态性静态图频繁增删内存限制宽松紧张这张表不是绝对的实际决策往往是多个因素的综合。比如一个顶点数不多但非常稀疏的图虽然规模小但用邻接表可能代码更简洁。关键是想清楚你的瓶颈在哪里。5. 实战中的性能陷阱与优化技巧5.1 内存占用的真实计算与优化很多人对内存占用的估计是偏乐观的因为忽略了编程语言本身的开销。以 Python 为例一个整数对象大约占 28 个字节一个列表元素是指向对象的指针占 8 个字节。所以一个1000 x 1000的邻接矩阵如果存的是 Python 整数实际内存是 100万 × (28 8) 字节大约 36 MB而不是直觉上的 1 MB 或 4 MB。如果换成array模块或者 NumPy 的int8数组内存可以降到 1 MB。这就是为什么在性能敏感的场景选择合适的数据类型至关重要。C 里用bool数组每个元素占 1 字节用bitset每个元素只占 1 位空间直接缩小 8 倍。邻接表也有类似问题。Python 里每个列表都有额外开销存储大量小列表时开销累积起来很可观。一个优化技巧是如果顶点度数普遍很小可以用一个扁平数组加偏移量来存避免大量小对象的开销。这就是链式前向星的思想。5.2 遍历效率的差异与缓存友好性除了空间遍历效率也受存储结构影响而且这个影响往往被低估。邻接矩阵遍历一个顶点的邻居需要扫描整行 n 个元素。虽然每个元素访问是 O(1)但 n 次访问累加起来是 O(V)。对于稀疏图大部分访问都是无效的白白浪费了 CPU 周期。更糟糕的是如果矩阵很大扫描一行会跨越很多内存页缓存命中率低实际耗时可能远超理论值。邻接表遍历邻居只访问实际存在的边访问次数等于度数。而且邻居数据在内存里是连续的列表的情况下缓存友好实际执行速度往往比理论分析还要好。我做过一个对比测试一个一万节点、平均度数 5 的稀疏图用邻接矩阵做一次全图 BFS耗时约 2.3 秒用邻接表做同样的 BFS耗时约 0.08 秒。差距接近 30 倍。这个差距在更大规模的数据上还会继续拉大。所以如果你的算法核心是遍历邻接表几乎是必然的选择。只有在需要频繁做 O(1) 边查询时邻接矩阵的优势才能体现出来。5.3 几个容易踩的坑与规避方法第一个坑是无向图的对称赋值遗漏。前面提过这里再强调一次。无向图添加边 (u, v) 时必须同时设置adj[u][v]和adj[v][u]。漏掉任何一个图就变成了有向图算法结果会错得莫名其妙。规避方法是在add_edge里统一处理不要在多处手动赋值。第二个坑是自环和重边的处理。邻接矩阵里自环就是matrix[i][i] 1重边会覆盖只保留最后一次的值。邻接表里自环就是adj[i]里包含 i重边会导致列表里出现重复元素。如果你的算法对重边敏感比如求最短路径需要在添加边时判断是否已存在或者选择保留权重最小的那条。这个逻辑要在建图阶段就想清楚不要等到算法出错再回头查。第三个坑是顶点编号不连续。邻接矩阵要求顶点编号是 0 到 n-1 的连续整数如果数据里的顶点 ID 是字符串或者不连续的整数必须先做映射。邻接表用字典实现的话没有这个限制但如果用列表实现同样需要映射。映射本身不难但要记得维护一个反向映射方便输出结果时还原成原始 ID。第四个坑是大规模图的递归深度。用 DFS 遍历大图时递归实现可能导致栈溢出。Python 默认递归深度限制是 1000超过就会报错。解决办法是改用迭代实现用显式的栈来模拟递归。这个问题在邻接矩阵和邻接表上都存在但邻接表因为遍历效率高更容易在短时间内深入很多层反而更容易触发。6. 从存储结构到算法BFS 与 DFS 的两种写法6.1 基于邻接矩阵的遍历实现先看邻接矩阵上的 BFS。核心逻辑是维护一个队列从起点开始每次取出一个顶点扫描它的整行把未访问的邻居加入队列。from collections import deque def bfs_matrix(matrix, start): n len(matrix) visited [False] * n queue deque([start]) visited[start] True order [] while queue: u queue.popleft() order.append(u) for v in range(n): if matrix[u][v] ! 0 and not visited[v]: visited[v] True queue.append(v) return order这段代码里for v in range(n)就是扫描整行的过程。即使 u 只有一个邻居也要循环 n 次。这就是邻接矩阵遍历效率低的根源。DFS 的递归写法类似只是把队列换成递归调用。def dfs_matrix(matrix, start, visitedNone, orderNone): if visited is None: visited [False] * len(matrix) if order is None: order [] visited[start] True order.append(start) for v in range(len(matrix)): if matrix[start][v] ! 0 and not visited[v]: dfs_matrix(matrix, v, visited, order) return order同样每次递归都要扫描整行。对于稀疏图这是巨大的浪费。6.2 基于邻接表的遍历实现换成邻接表遍历逻辑不变但内层循环只遍历实际存在的邻居。def bfs_adjlist(adj, start): visited {start} queue deque([start]) order [] while queue: u queue.popleft() order.append(u) for v, _ in adj.get(u, {}).items(): if v not in visited: visited.add(v) queue.append(v) return order注意这里for v, _ in adj.get(u, {}).items()只迭代 u 的实际邻居次数等于度数。对于稀疏图这比扫描整行快得多。DFS 的迭代写法用显式栈def dfs_adjlist(adj, start): visited set() stack [start] order [] while stack: u stack.pop() if u in visited: continue visited.add(u) order.append(u) for v, _ in adj.get(u, {}).items(): if v not in visited: stack.append(v) return order这里有一个细节迭代版 DFS 在入栈时不能立即标记 visited否则可能重复入栈。正确的做法是出栈时判断或者入栈时标记但允许重复入栈后跳过。两种方式都可以但要注意区别。6.3 遍历顺序差异带来的实际影响同一个图用邻接矩阵和邻接表做 BFS得到的遍历顺序可能不同。这不是 bug而是因为邻居的访问顺序不同。邻接矩阵扫描整行邻居是按顶点编号从小到大访问的。邻接表遍历邻居列表顺序取决于添加边的顺序。如果添加顺序和编号顺序不一致遍历结果就会不同。这个差异在某些场景下会影响结果。比如求最短路径时如果有多条等长路径不同的遍历顺序可能导致返回不同的路径虽然长度相同。如果业务对路径的具体走法有要求就需要统一遍历顺序。解决办法是在建图时对邻居列表排序或者在选择算法时明确顺序要求。我在一个路径规划的项目里就遇到过这个问题。同样的图两次运行返回的路径不一样排查了半天才发现是邻接表里邻居顺序不稳定导致的。后来在添加完所有边后对每个邻居列表做了排序问题才解决。这个经验告诉我只要算法对顺序敏感就必须显式控制顺序不能依赖数据结构的默认行为。7. 我个人的选型心得与几个实用建议聊了这么多原理和代码最后分享几点我在实际工作中总结出来的经验可能和教科书上的说法不完全一样但都是踩过坑之后得出的。第一点不要过早优化存储结构。很多同学一上来就纠结用矩阵还是邻接表其实在数据规模不大的时候两者的差异微乎其微。先把算法跑通确认瓶颈确实在存储结构上再动手优化。我见过太多人花大量时间优化了一个根本不是瓶颈的地方真正的性能问题反而被忽略了。第二点优先考虑代码可读性和可维护性。邻接矩阵的代码通常比邻接表简单调试也更容易。如果项目对性能要求不是极致用邻接矩阵能让团队里其他人更快看懂你的代码。性能优化可以留到确实需要的时候再做而且往往有比换存储结构更有效的优化手段。第三点混合使用也是一种选择。有些场景下同时维护邻接矩阵和邻接表是合理的。比如用矩阵做快速的边查询用表做高效的邻居遍历。代价是内存翻倍建图时间增加但如果查询和遍历都是热点操作这个代价是值得的。关键是要评估清楚两种操作的频率比例。第四点测试用例要覆盖边界情况。空图、单顶点图、完全图、只有一条边的图、有自环的图、有重边的图这些都要测。我踩过最深的坑是一个只有两个顶点一条边的图因为代码里有个if n 2的判断直接把这个情况跳过了导致结果为空。边界情况往往是最容易出 bug 的地方也是最容易被忽略的地方。第五点关注数据的实际分布。理论上的稀疏图和稠密图和实际数据的分布可能差别很大。有些图整体稀疏但存在少数度数极高的“超级节点”。这种图用邻接表时超级节点的邻居列表会非常长遍历它仍然很慢。针对这种情况可以考虑对高度数节点做特殊处理比如单独存储或者用更紧凑的结构。这个优化思路在社交网络分析里很常见因为确实存在关注数几十万的大 V 节点。存储结构的选择没有银弹邻接矩阵和邻接表各有各的适用场景。理解它们的底层原理和性能特征结合具体的数据规模、图的稠密程度、核心操作类型来决策才能写出既正确又高效的代码。希望这篇内容能帮你在下次遇到图相关的问题时少走一些弯路。