1. 从“图”到“矩阵”为什么我们需要数学表示聊图论很多人一开始都会被那些点和线组成的“图”吸引觉得直观又好玩。但当你真正想用计算机去处理一个社交网络的关系、分析一个电路的通路或者优化一个物流网络的路径时光靠画图是远远不够的。你会发现面对成百上千个节点和边人脑很难进行系统性的计算和推理。这时候我们就需要一种更强大、更精确的语言来描述图——这就是矩阵。矩阵本质上是一个数字的矩形阵列。它看起来冰冷抽象但却是连接图论直观世界与计算机可计算世界之间最坚固的桥梁。把图“翻译”成矩阵我们就能借用线性代数这个庞大的工具库对图进行量化分析、高效存储和复杂运算。今天要深入聊的“邻接矩阵”和“关联矩阵”就是两种最经典、也最实用的“翻译”方法。它们从不同的角度刻画了图中顶点与边的关系各有各的擅长场景和内在逻辑。理解这两种矩阵不仅仅是记住它们的定义和怎么填0、1。更重要的是理解它们背后的设计哲学邻接矩阵关注的是顶点与顶点之间的直接关系它回答的问题是“两点之间有没有边相连”而关联矩阵关注的是顶点与边之间的隶属关系它回答的问题是“这条边连接了哪两个顶点或关联了哪个顶点”。这个根本性的视角差异决定了它们在图算法、存储效率和应用场景上的巨大不同。接下来我们就抛开教科书式的定义从实际应用和底层逻辑出发把这两种矩阵掰开揉碎了讲清楚。2. 邻接矩阵最直观的“谁和谁认识”关系表当我们想描述一个社交网络里用户之间的好友关系时最自然的想法是什么很可能是列一个巨大的表格横轴和纵轴都是所有用户如果用户A和用户B是好友就在他们交叉的格子里打个勾或者填个1。这个想法就是邻接矩阵的核心。2.1 定义与构建从关系图到数字方阵给定一个具有n个顶点的图无论有向还是无向它的邻接矩阵A就是一个n×n的方阵。这个矩阵的第i行第j列的元素a_ij表示从顶点i到顶点j的边的“情况”。对于最常见的简单无向图边没有方向且没有自环和重边如果顶点i和顶点j之间有边相连则 a_ij 1。如果顶点i和顶点j之间没有边相连则 a_ij 0。由于是无向图边(i, j)和边(j, i)是同一条边所以矩阵一定是对称的即 a_ij a_ji。对于有向图如果存在一条从顶点i指向顶点j的弧有向边则 a_ij 1。否则为0。此时矩阵通常不再对称a_ij 1 不代表 a_ji 1这精确地刻画了方向的单向性。让我们用一个具体的无向图例子来构建。假设我们有4个人张三(1)、李四(2)、王五(3)、赵六(4)。他们的好友关系是张三和李四是好友张三和王五是好友李四和赵六是好友。这个关系图很简单。首先我们列出所有顶点作为行和列的标签。然后按照关系填空(1,2)张三和李四是好友填1。(1,3)张三和王五是好友填1。(2,4)李四和赵六是好友填1。根据对称性(2,1), (3,1), (4,2)也填1。其他所有关系包括自己对自己主对角线因为没有自环全部填0。最终得到的邻接矩阵A如下1 2 3 4 1 [0, 1, 1, 0] 2 [1, 0, 0, 1] 3 [1, 0, 0, 0] 4 [0, 1, 0, 0]这个矩阵一眼看过去就能立刻知道整个网络的直接连接关系。比如看第一行[0,1,1,0]就知道顶点1张三和顶点2、3有连接。注意在实际编程中比如用Python的NumPy或纯二维数组我们通常直接用顶点的索引0,1,2,3来代表顶点矩阵的构建就是基于这些索引进行循环赋值而不需要显式的标签。上述演示是为了理解方便。2.2 邻接矩阵的幂运算揭示“间接关系”与路径发现邻接矩阵最精妙的一个性质体现在它的幂运算上。这个性质不是数学游戏而是解决“通过多少步可以认识某人”这类问题的关键。定理设A是一个图的邻接矩阵那么A^kA的k次幂中的元素(A^k)_ij其值等于从顶点i到顶点j的长度为k的路径的条数。什么是“路径”就是从一个顶点出发沿着边连续移动k次到达另一个顶点所经过的顶点序列中间点可以重复但边通常不允许重复在简单路径中顶点也不重复。这个定理的证明基于矩阵乘法的定义本质上是一种计数原理的叠加。让我们用上面的矩阵A来验证一下。计算A^2 A × AA^2 [0,1,1,0] [0,1,1,0] [2,0,0,1] [1,0,0,1] × [1,0,0,1] [0,2,1,0] [1,0,0,0] [1,0,0,0] [0,1,1,0] [0,1,0,0] [0,1,0,0] [1,0,0,1]看结果矩阵A^2(A^2)_11 2。这意味着从顶点1张三到顶点1长度为2的路径有2条。验证一下1-2-1 和 1-3-1。(A^2)_14 1。这意味着从顶点1到顶点4赵六长度为2的路径有1条。验证1-2-4。(A^2)_23 1。这意味着从顶点2李四到顶点3王五长度为2的路径有1条。验证2-1-3。这个性质非常强大。它意味着如果我们想找出图中任意两点间是否存在长度不超过k的路径或者想计算两点间的距离最短路径长度理论上可以通过计算A, A^2, A^3, ... 直到A^k来实现。当图规模不大时这为一些算法提供了思路。例如图中两个顶点是否连通即是否存在任意长度的路径可以通过检查矩阵序列 (I A A^2 ... A^(n-1)) 是否在对应位置非零来判断这关联着图的传递闭包概念。2.3 空间与时间复杂度分析优势与代价邻接矩阵的优点显而易见直观、查询速度快。判断任意两个顶点i和j之间是否有边只需要O(1)的时间访问矩阵元素A[i][j]即可。这对于需要频繁进行此类查询的应用场景如实时关系判断是巨大的优势。但是它的缺点也同样突出主要在于空间消耗。存储一个n个顶点的图需要n^2个存储单元。对于一个有10000个顶点的稀疏图比如大多数社交网络每个人直接认识的人有限矩阵中会有大量的0这造成了巨大的空间浪费。在添加或删除边时操作是O(1)的只需要修改一个矩阵元素。但是添加或删除一个顶点则非常昂贵可能需要重新分配并复制整个n^2的矩阵时间复杂度为O(n^2)。因此邻接矩阵更适用于稠密图边数接近顶点数平方的量级或者顶点规模不大但需要极快边查询速度的场景。对于大型稀疏图我们接下来要讨论的关联矩阵以及更常用的邻接表才是更合适的选择。3. 关联矩阵从“边”的视角洞察图的构成如果说邻接矩阵是“顶点中心”的视图那么关联矩阵就是“边中心”的视图。它不再关心顶点之间是否直接“认识”而是关心每一条边具体“连接”或“关联”了哪些顶点。这种视角在处理电路网络、关联规则分析等场景时尤为自然。3.1 定义与构建建立顶点与边的关联关系对于一个具有n个顶点、m条边的图同样先考虑无向图其关联矩阵B是一个n×m的矩阵。矩阵的行代表顶点列代表边。矩阵元素b_ij定义如下如果顶点i是边j的一个端点则 b_ij 1。否则b_ij 0。注意在无向图中一条边恰好关联两个顶点端点所以关联矩阵的每一列对应一条边恰好有两个1其余全为0。这个性质非常关键。沿用之前的社交网络例子但这次我们明确给边编号。顶点依然是1,2,3,4。边有三条边e1: 连接顶点1和2张三-李四边e2: 连接顶点1和3张三-王五边e3: 连接顶点2和4李四-赵六现在我们构建关联矩阵B。行是顶点1到4列是边e1, e2, e3。对于边e1连接1和2在顶点1行e1列填1顶点2行e1列填1。对于边e2连接1和3在顶点1行e2列填1顶点3行e2列填1。对于边e3连接2和4在顶点2行e3列填1顶点4行e3列填1。其他所有位置填0。得到的关联矩阵B如下e1 e2 e3 1 [1, 1, 0] 2 [1, 0, 1] 3 [0, 1, 0] 4 [0, 0, 1]观察这个矩阵每一列确实都有且仅有两个1对应一条边的两个端点。从行来看第一行有两个1说明顶点1关联了两条边e1和e2这与张三有李四和王五两个好友的事实一致。3.2 有向图的关联矩阵引入方向与符号对于有向图关联矩阵需要体现边的方向。通常我们使用顶点-弧关联矩阵并引入符号来区分边的“出”和“入”。常见的定义是如果顶点i是弧j的起点则 b_ij 1。如果顶点i是弧j的终点则 b_ij -1。否则b_ij 0。这样每一列对应一条弧就有一个1和一个-1其余为0。这个表示法在电路理论基尔霍夫电流定律和网络流问题中有着根本性的重要性因为矩阵的每一列向量之和为0体现了“流量守恒”的雏形。假设一个有向图顶点1-2弧a1顶点1-3弧a2顶点2-4弧a3。其关联矩阵B_d如下a1 a2 a3 1 [1, 1, 0] 2 [-1,0, 1] 3 [0, -1, 0] 4 [0, 0, -1]可以看到每一列都满足“1 (-1) 0”的模式。3.3 关联矩阵的性质与应用场景关联矩阵虽然不如邻接矩阵常用但它有一些独特的性质和适用场景与度序列的关系在无向图的关联矩阵B中矩阵B的行和即每一行所有元素的和等于对应顶点的度数。因为行和就是计算这个顶点在所有边中作为端点的次数。在我们上面的例子中第一行和为2顶点1的度数为2第二行和也为2顶点2的度数也是2第三、四行和为1对应度数为1。这个性质非常直观。用于电路分析这是关联矩阵的经典应用。在电路网络中顶点代表电路节点边代表支路电阻、电源等。关联矩阵通常称为关联矩阵A是建立基尔霍夫电流定律KCL方程的基础。对于有n个节点、b条支路的电路其关联矩阵是(n-1)×b的通常去掉接地点所在行每一列对应一条支路1代表电流流出该节点-1代表电流流入该节点。KCL方程可以简洁地表示为A * i 0其中i是支路电流向量。这个线性方程组是求解电路的基础。空间效率对于稀疏图关联矩阵的存储空间是O(n*m)。在边数m远小于n^2的稀疏图中它比邻接矩阵的O(n^2)要节省空间尤其是当使用稀疏矩阵格式存储时。然而它仍然不如邻接表空间O(nm)高效且查询“两个顶点之间是否有边”的操作效率较低需要遍历列。关联矩阵的秩对于一个具有n个顶点、c个连通分量的无向图其关联矩阵B的秩为n - c。这个性质与图的生成树、回路矩阵等概念紧密相关是图论中更深入的主题。4. 邻接矩阵与关联矩阵的深度对比与选型指南理解了两种矩阵的构造和性质后我们需要一个清晰的对比以便在实际问题中做出正确选择。这个选择不是非此即彼而是基于你的核心操作是什么。4.1 核心视角与信息编码的差异这是最根本的区别决定了它们的一切。邻接矩阵 (Adjacency Matrix)编码的是顶点对之间的二元关系。它的核心问题是“顶点i和顶点j是否直接相邻” 矩阵元素a_ij的值直接回答了这个问题。它丢失了“边”作为独立实体的身份边被抽象为顶点对关系的一个布尔值或权值。关联矩阵 (Incidence Matrix)编码的是顶点与边之间的隶属关系。它的核心问题是“边j关联了哪些顶点” 矩阵的列向量完整地描述了一条边。它保留了边作为独立实体的身份但弱化了顶点之间的直接关系。用一个简单的类比想象一个公司组织架构图。邻接矩阵就像一张“直接汇报关系表”只记录谁直接向谁汇报。关联矩阵就像一份“项目参与名单”记录每个项目边有哪些员工顶点参与。4.2 存储效率与操作复杂度对比我们可以用一个表格来清晰对比特性邻接矩阵 (A)关联矩阵 (B)说明与启示矩阵维度n × n (方阵)n × m (矩形阵)A的大小由顶点数决定B的大小由顶点和边数共同决定。稀疏图存储效率极低大量0元素浪费空间。效率较低但优于A。每列仅两个非零元(无向图)。对于大型稀疏图两者都不是最优应首选邻接表。稠密图存储效率高几乎无浪费。效率低于A因为m≈n^2时B有约2n^2个非零元A只有n^2个。对于完全图或接近完全的图邻接矩阵空间更优。查询边(i,j)O(1)直接访问A[i][j]。O(m)最坏需扫描所有列检查是否同时关联i和j。如果需要频繁判断两点间是否有边A是绝对王者。查询顶点v的邻居O(n)需要扫描第v行或列。O(m)需要扫描所有列找到包含v的边再找出边的另一端点。两者效率都不高。邻接表对此操作是O(degree(v))最优。添加/删除边O(1)修改一个元素。O(1)修改一列中的两个元素。两者都很快。添加/删除顶点O(n^2)可能需重建整个矩阵。O(n*m)添加顶点加一行删除顶点复杂。动态增减顶点的场景下两者代价都高邻接表更灵活。实操心得这个对比表是选型的核心依据。在做课程设计或小型项目时如果题目明确给出了顶点数n且n较小比如100并要求实现某些基于矩阵运算的算法如计算路径数、传递闭包那么邻接矩阵是首选。如果问题更关注边本身的性质如给边赋权、计算边覆盖或者背景是电路网络那么关联矩阵更自然。但对于绝大多数ACM竞赛、大型网络分析或图数据库场景邻接表或其变体如链式前向星才是真正的主流和首选存储结构因为它完美平衡了稀疏图下的空间和时间效率。4.3 典型应用场景分野基于它们的特性两者擅长的领域有所不同邻接矩阵的典型场景图论定理证明与数学推导许多图论定理如关于图谱、矩阵树定理的表述和证明都基于邻接矩阵或拉普拉斯矩阵由邻接矩阵和度矩阵导出。需要快速判断边存在的算法例如Floyd-Warshall全源最短路径算法其核心就是三重循环操作邻接矩阵或其扩展的权值矩阵。稠密图的小规模计算当图非常稠密边数接近n(n-1)/2且顶点数不多时邻接矩阵的简单性和操作速度优势明显。图神经网络 (GNN)在GNN的许多实现中邻接矩阵是输入特征之一用于定义节点的邻居关系以便进行消息传递和聚合。关联矩阵的典型场景电路网络分析如前所述是建立KCL方程、分析网络拓扑的基石。线性规划与网络流问题在运输问题、分配问题等建模中约束条件常常体现为“一个顶点关联的所有边的流量之和满足某种关系”这天然对应关联矩阵的行。关联规则与超图关联矩阵可以很自然地推广到超图一条边可以关联多个顶点用于数据挖掘中的关联规则分析。某些特定图算法例如用于寻找图的所有生成树或计算回路空间的算法有时基于关联矩阵的代数性质更为方便。5. 从理论到代码实现与常见问题剖析理论说得再透不动手实现一遍也是空中楼阁。这里我们用Python来简单实现这两种矩阵的构建并讨论几个实际编码中必然会遇到的问题。5.1 邻接矩阵的Python实现与细节假设我们通过输入节点数n和边数m以及边的列表来构建一个无向图的邻接矩阵。def build_adjacency_matrix(n, edges): 构建无向图的邻接矩阵。 Args: n: 顶点数顶点编号从0到n-1。 edges: 边的列表每个元素为(u, v)的元组。 Returns: 一个二维列表表示的n x n邻接矩阵。 # 初始化n x n的零矩阵 adj_matrix [[0] * n for _ in range(n)] for u, v in edges: # 假设输入是有效的且为简单图无自环 adj_matrix[u][v] 1 adj_matrix[v][u] 1 # 无向图对称赋值 return adj_matrix # 示例对应之前张三(0)、李四(1)、王五(2)、赵六(3)的例子 n 4 edges [(0, 1), (0, 2), (1, 3)] # 边0-1, 0-2, 1-3 adj_mat build_adjacency_matrix(n, edges) for row in adj_mat: print(row) # 输出 # [0, 1, 1, 0] # [1, 0, 0, 1] # [1, 0, 0, 0] # [0, 1, 0, 0]几个关键细节与避坑点顶点编号从0还是1开始在绝大多数编程语言和算法中数组索引从0开始。因此内部存储时顶点编号应使用0-based0到n-1。如果输入是1-based的如题目常说“节点分别用1,2,...,n表示”在存入矩阵前一定要先减1转换。这是一个非常常见的错误来源。空间初始化[[0]*n]*n这种写法是错误的它创建了n个引用到同一个列表的引用修改其中一行会影响所有行。必须使用列表推导[[0]*n for _ in range(n)]来创建独立的子列表。有向图处理对于有向图在循环中只执行adj_matrix[u][v] 1而不执行对称赋值。带权图如果边有权重则将矩阵初始化为一个很大的数如float(inf)代表无穷远或无连接然后将adj_matrix[u][v]赋值为权重w。对角线通常初始化为0自己到自己的距离为0。5.2 关联矩阵的Python实现与细节关联矩阵的构建需要明确边的编号。我们假设输入是顶点数n以及一个边列表每条边附带一个唯一的标识符或直接用索引作为编号。def build_incidence_matrix(n, edges): 构建无向图的关联矩阵。 Args: n: 顶点数顶点编号从0到n-1。 edges: 边的列表每个元素为(u, v)的元组。边的编号即其在列表中的索引。 Returns: 一个二维列表表示的n x m关联矩阵m为边数。 m len(edges) inc_matrix [[0] * m for _ in range(n)] for edge_idx, (u, v) in enumerate(edges): inc_matrix[u][edge_idx] 1 inc_matrix[v][edge_idx] 1 return inc_matrix # 示例 n 4 edges [(0, 1), (0, 2), (1, 3)] # 三条边编号分别为0,1,2 inc_mat build_incidence_matrix(n, edges) for row in inc_mat: print(row) # 输出 # [1, 1, 0] # [1, 0, 1] # [0, 1, 0] # [0, 0, 1]关联矩阵实现的注意事项边编号的确定性关联矩阵依赖于稳定的边编号。在构建时必须确保每条边有一个唯一且固定的索引通常就用它在输入列表中的位置。有向图关联矩阵实现时需要根据边的方向赋值1或-1。例如对于有向边(u, v)执行inc_matrix[u][edge_idx] 1和inc_matrix[v][edge_idx] -1。空间考虑关联矩阵通常更稀疏。在Python中对于大型图可以考虑使用scipy.sparse库中的稀疏矩阵格式如lil_matrix或csr_matrix来存储可以节省大量内存。5.3 邻接矩阵幂运算的实现与意义验证我们可以通过矩阵乘法来验证邻接矩阵幂的意义。这里使用NumPy库来简化操作。import numpy as np # 使用之前的邻接矩阵 adj_mat np.array([[0, 1, 1, 0], [1, 0, 0, 1], [1, 0, 0, 0], [0, 1, 0, 0]]) # 计算 A^2 A_squared np.linalg.matrix_power(adj_mat, 2) print(A^2 (矩阵幂):) print(A_squared) # 输出应与我们之前手动计算的一致 # [[2 0 0 1] # [0 2 1 0] # [0 1 1 0] # [1 0 0 1]] # 手动验证路径数计算从顶点0到顶点3的长度为2的路径 # 即找所有中间节点k使得 A[0][k]1 且 A[k][3]1 paths [] for k in range(4): if adj_mat[0][k] 1 and adj_mat[k][3] 1: paths.append((0, k, 3)) print(f\n从顶点0到顶点3长度为2的路径有 {len(paths)} 条: {paths}) # 输出从顶点0到顶点3长度为2的路径有 1 条: [(0, 1, 3)] # 这正好对应 A_squared[0, 3] 1这个简单的验证程序不仅确认了定理也展示了如何通过编程来探索图的性质。对于更大的图手动寻找路径是不现实的但矩阵运算可以在O(n^3)的时间内通过矩阵乘法的优化可以更低告诉我们所有顶点对之间长度为k的路径总数。6. 超越基础从矩阵表示看图的连通性与谱当我们掌握了这两种基本的矩阵表示后我们的视角可以再提升一个层次看看它们如何引向图论中更深奥但也更迷人的领域图的连通性分析和图谱理论。这部分内容可能不会出现在所有初级课程中但了解它们能让你明白这些矩阵不仅仅是存储工具更是强大的分析武器。6.1 利用矩阵幂探测连通性与距离之前提到A^k的(i, j)元素表示从i到j长度为k的路径数。这个性质可以直接用来解决一些实际问题判断连通性如果对于图中所有顶点对(i, j)都存在某个k使得(A^k)_ij 0那么这个图就是连通的。实际上如果图是连通的其直径任意两点间最短路径的最大值为d那么检查矩阵序列I, A, A^2, ..., A^d就足够了。因为最短路径长度不会超过n-1所以计算S I A A^2 ... A^(n-1)如果S的所有非对角元素都大于0则图连通。这提供了另一种判断连通性的代数方法虽然效率不如DFS/BFS。计算最短路径长度无权图的最短路径长度就是使得(A^k)_ij 0的最小k值。我们可以通过迭代计算A, A^2, A^3,...直到目标位置非零。这本质上是广度优先搜索(BFS)的矩阵模拟。对于小型稠密图这种方法的代码实现可能很简洁。6.2 图的谱邻接矩阵特征值揭示的秘密这是邻接矩阵理论中最优美的部分之一。一个图的邻接矩阵A的特征值集合称为这个图的谱。这些特征值包含了关于图结构的丰富信息。特征值的范围对于无向图A是实对称矩阵其特征值都是实数。并且最大特征值λ_max与图的度密切相关λ_max ≤ ΔΔ为最大度数且λ_max ≥ 平均度数。二分图判定一个图是二分图当且仅当其邻接矩阵的谱关于原点对称即如果λ是特征值那么-λ也是特征值。这是一个非常代数的判定条件。图的扩张性与连通性第二大特征值λ2按模从大到小排序的大小与图的“连通好坏”程度紧密相关。λ2与最小特征值λ_min的差距谱隙越大图通常扩张性越好也就是更“难以被分割”。这个性质在社区发现、聚类分析以及构建稳健的网络中非常重要。图谱与图神经网络在现代图神经网络中图的拉普拉斯矩阵L D - A其中D是度矩阵的谱特征值和特征向量被用来定义图上的傅里叶变换从而将卷积操作推广到图数据上。这是将深度学习应用于非欧几里得数据如图、社交网络的基础。虽然计算大规模图的特征值开销很大但谱理论为我们理解图的整体结构提供了强有力的数学工具。它告诉我们一个看似简单的0-1矩阵其内部蕴含的数学信息是如此深刻。6.3 关联矩阵与线性代数行空间、零空间与图的空间关联矩阵B同样有着深刻的代数意义它将图的结构与线性代数中的向量空间联系起来。行空间与割空间关联矩阵B的行向量张成的空间其维度是n-cc为连通分量数。这个空间与图中所有“割”的集合即那些将顶点集划分为两部分的边集有着对应关系。零空间与环空间关联矩阵B的零空间即满足B*x0的向量x的集合的维度是m - n c。这个空间中的向量可以解释为给图中每条边分配一个权值使得每个顶点关联的所有边的权值代数和为零。这恰好对应了图中“环”或“回路”的概念。零空间的一组基对应着一组基本回路。矩阵树定理这个著名的定理指出一个连通图的生成树数目等于其拉普拉斯矩阵L的任意一个代数余子式的值。而拉普拉斯矩阵L可以通过关联矩阵表示对于无向图有 L B * B^T。这建立了关联矩阵、拉普拉斯矩阵与图计数问题之间的桥梁。这些内容相对进阶但它们展示了图论不仅仅是画点和线它可以通过矩阵这个工具与线性代数、组合数学甚至物理中的电路理论产生深刻的联系。理解这些联系能让你在面对复杂网络问题时拥有更多可用的思维模型和工具。7. 总结与个人实践建议走完了从定义、构建、对比到代码实现和理论延伸的整个过程我们再回头审视“邻接矩阵”和“关联矩阵”这两个概念。它们绝不是两个需要死记硬背的定义而是两种不同的“观察镜”。邻接矩阵是“顶点关系镜”擅长快速回答顶点间的直接关联关联矩阵是“边构成镜”擅长描述边与顶点的具体连接关系。在我自己学习和使用图论的过程中有几点很深的体会 第一不要死磕一种表示法。很多初学者学会了邻接矩阵后就试图用它解决所有问题这在面对稀疏图时会导致灾难。一定要根据问题的核心操作是频繁查边还是遍历邻居或是进行矩阵运算和图的规模、密度来灵活选择。邻接表在大多数算法竞赛和工程实践中是更通用的选择但邻接矩阵在理论推导和小规模稠密图运算中无可替代。 第二亲手实现一遍是理解的关键。无论是用Python、C还是Java自己写代码构建这两个矩阵处理一下顶点编号从1开始的问题尝试计算一下矩阵的幂你会对“对称性”、“每一列两个1”这些性质有肌肉记忆般的理解。遇到bug的过程就是深化理解的过程。 第三尝试探索它们之间的联系。比如你可以写程序验证无向图的邻接矩阵A和关联矩阵B之间是否满足 A B * B^T - D其中D是度矩阵的对角线部分这个等式在某些条件下是成立的。通过这样的探索你能把孤立的知识点串联成网。最后虽然关联矩阵在实际编程中不如邻接矩阵和邻接表常用但它在特定领域如电路、网络流是基石。理解它能让你在遇到这些领域的问题时不至于感到完全陌生。图论的世界远不止这两种矩阵还有邻接表、十字链表、邻接多重表等多种存储结构以及基于它们的无数精妙算法。把这两种矩阵吃透就为你进一步探索这个广阔世界打下了最坚实的代数基础。下次当你面对一个网络问题时不妨先问自己我是更关心“谁和谁直接有关”还是更关心“每个连接具体是谁和谁”答案会自然地指引你该拿起哪一副“观察镜”。