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。添加/删除顶点成本高增加一个顶点意味着需要重新分配一个(n1) x (n1)的矩阵并拷贝数据成本是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中我强烈推荐使用vectorvectorint或vectorvectorpairint, 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(ne)。如果需要频繁查询入度例如在拓扑排序、计算网页的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编码速度极快。用一个二维数组所有操作都简化为数组赋值和访问不容易出错。理由2O(1)的边查询。很多基于动态规划的图算法如Floyd-Warshall全源最短路径需要频繁读取任意两点间的距离矩阵的随机访问优势无可替代。理由3空间可以接受。500x500的矩阵在大多数语言中只占约1MB假设int类型的内存完全在限制内。实现注意点对于有权图记得用INF一个很大的数如0x3f3f3f3f初始化矩阵来表示“无边”。对于无向图添加边务必设置对称的两个位置。5.2 场景二大规模稀疏网络与工程系统典型场景社交网络分析用户作为顶点关注关系作为边网页爬虫URL作为顶点超链接作为有向边推荐系统用户-物品二分图知识图谱。选型与理由邻接表是绝对的主流。理由1内存是硬约束。百万顶点、千万边的图矩阵需要TB级别内存而邻接表可能只需要GB级别。理由2遍历操作是核心。诸如广度优先搜索BFS、深度优先搜索DFS、Dijkstra最短路径等算法核心操作是遍历顶点的邻居。邻接表的O(degree)效率远高于矩阵的O(n)。理由3易于扩展。动态添加新顶点或新边非常自然。进阶技巧使用vectorvectorpairint, int存储带权图pair中第一个元素是邻居顶点第二个是权重。如果需要去重边例如多次添加同一条边可以考虑用vectorunordered_setint但会牺牲一些遍历的缓存性能。对于超大规模图可能需要使用压缩稀疏行CSR格式这是一种将邻接表扁平化存储的工业级格式能进一步压缩空间并提升缓存命中率。5.3 场景三需要快速查询入度的有向图处理典型场景任务调度拓扑排序计算有向图中顶点的PageRank或影响力分析数据流或依赖关系。选型与理由邻接表出边表 入度数组。理由拓扑排序的Kahn算法核心就是不断移除入度为0的顶点。我们既需要快速遍历一个顶点的所有出边邻接表擅长又需要快速获取和修改任意顶点的入度入度数组擅长。维护一个单独的inDegree数组空间开销仅为O(n)是性价比最高的方案。操作示例// 假设有n个顶点边列表为vectorpairint, int edges vectorvectorint adj(n); // 邻接表 vectorint 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, vectorvectorint matrix, vectorbool 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, vectorvectorint adj, vectorbool 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, isDirectedfalse)的辅助函数是个好习惯。邻接表初始化别忘了使用vectorvectorint adj(n)后adj里已经有n个空的vector了。但如果用vectorint adj[n]C风格数组或ListListInteger adj new ArrayList(n)Java记得要为每个位置初始化一个新的空列表对象否则会导致空指针异常。根据操作频率选型不要死记“稀疏用表稠密用阵”。问问自己我的核心操作是什么是遍历邻居选表还是随机查边选阵或哈希表亦或是查入度可能需要额外数组分析清楚操作模式选择才能最优。空间与时间的权衡邻接表省空间但牺牲了常数时间的查边。邻接矩阵查边快但浪费空间。在内存充裕的小规模问题中矩阵的简单性是巨大优势在大数据场景下表的空间效率是生存之本。有时候为了特定操作如快速查边在邻接表里套一个哈希集合是一种用空间换时间的实用折中。测试时从简单图开始调试图算法时先用一个3-5个顶点的小图手工画出它的矩阵和邻接表表示然后单步跟踪你的代码看数据结构的构建和算法的每一步是否符合预期。这比直接在大图上抓瞎要高效得多。图的基础表示是图论算法和应用的基石。理解邻接矩阵和邻接表不仅仅是记住两种数据结构更是理解一种“空间换时间”或“时间换空间”的经典权衡思想。下次当你面对一个图问题时先花一分钟思考一下图的规模、密度和核心操作再决定掏出哪一把“工具”你的代码效率和问题解决能力都会提升一个档次。