邻接矩阵：方阵中的连接情报

邻接矩阵：方阵中的连接情报

清晨的参谋部里，侦察兵陆续归队。参谋长把城市编号写在一张方格表的行头与列头，然后下达一条简单的登记规则：若城市甲与城市乙之间有路，就在对应格子画一道杠。全部登记完毕，方格表本身就是完整的地图——查任意两城的连接，只需看一眼格子。这张方格表就是邻接矩阵。本节讲清楚它的结构、代码实现、复杂度账单，以及一项常被埋没的本领：用矩阵的幂数通路。

方阵的构造规则

给图里的顶点编号，邻接矩阵是一个行数列数都等于顶点数的方阵。第 i 行第 j 列的格子填"顶点 i 到顶点 j 的边数"：无向简单图里这个值非零即一，且矩阵关于对角线对称（边无方向，甲连乙则乙连甲）；有向图里行表示出发、列表示到达，对称性消失；加权图可以把格子直接填成权重，另用零或无穷大表示"无边"——注意这两种"无边"记号在带负权时都要小心选择。

自环会让对角线格子加一；多重图把格子填成平行边的数目。所以严格说，邻接矩阵能表示多重图，却无法区分"哪一条"平行边——若边还携带各自的属性（如桥的名称），就必须配合边表补档。

复杂度账单

存储空间是矩阵最醒目的软肋：无论边多稀疏，格子总数都按顶点数的平方增长。顶点数上到十万，仅存零就得吃掉数十亿字节。反过来看它的强项：

• 查邻（顶点 i 与 j 之间是否有边）：直接读格子，常数时间。邻接表做不到这一点，得在邻居档案里翻找。
• 加边、删边：改一个格子，同样常数时间。
• 枚举邻居：扫一整行，耗时与顶点数成正比——即使某个顶点只有一两个邻居。这一条正是矩阵的命门：第 3 章的遍历、第 5 章的 Dijkstra 都要反复"枚举邻居"，矩阵会把每次枚举的账单开成顶点数级别，算法整体劣化。

把账单折算成直觉：矩阵的优势操作全部是"点对点"的（查一个格子、改一个格子），劣势操作全部是"沿邻居扩散"的（扫一行）。所以凡是算法骨架围着邻居扩散转的，矩阵都不合适；凡是围着稠密的两两关系转的（比如全源最短路、传递闭包、谱分析），矩阵反而如鱼得水。第 5 章 Floyd-Warshall 明确要求矩阵存储，不是巧合，而是算法本质就是矩阵上的逐格演算——到那时你会看到"表示法即算法舞台"这句话的字面含义。

代码实现

用嵌套列表手写邻接矩阵，并演示与边清单的互转：

class MatrixGraph:
    """无向加权图的邻接矩阵实现（多重边与自环亦可登记）"""
    def __init__(self, n):
        self.n = n
        self.adj = [[0] * n for _ in range(n)]   # 0 表示无边

    def add_edge(self, i, j, w=1):
        self.adj[i][j] += w
        self.adj[j][i] += w                       # 无向：对称登记

    def has_edge(self, i, j):
        return self.adj[i][j] != 0                 # 查邻：读一个格子

    def neighbors(self, i):
        return [j for j in range(self.n) if self.adj[i][j] != 0]  # 扫整行

    def degree(self, i):
        return sum(1 for j in range(self.n) if self.adj[i][j] != 0)

g = MatrixGraph(4)
for i, j in [(0,1),(1,2),(2,3),(0,3)]:
    g.add_edge(i, j)
print("1 和 2 相邻吗:", g.has_edge(0, 1))
print("2 的邻居:", g.neighbors(1))
​

再看矩阵的隐藏技能——幂计数。邻接矩阵的平方中，第 i 行第 j 列的值恰好等于"从 i 恰好走两条边到 j 的通路数"：每条两步通路都在中间点处被乘法数了一次。一般地，矩阵的 k 次幂数"恰好 k 步的通路数"。

import numpy as np

A = np.array([
    [0, 1, 0, 1],
    [1, 0, 1, 0],
    [0, 1, 0, 1],
    [1, 0, 1, 0],
])
print("A 的平方 =\n", A @ A)
print("从 1 经两步回到 1 的通路数:", (A @ A)[0, 0])   # 1→2→1 与 1→4→1
print("A 的立方 =\n", A @ A @ A)
​

把幂运算换成布尔矩阵乘（乘法改"与"、加法改"或"），得到的就是可达性：顶点 i 是否存在至多 k 步通路。再迭代到幂稳定，就得到传递闭包——第 5 章 Floyd-Warshall 的雏形正是在这张"演算纸"上展开的。矩阵与图论的这层血缘，来自把邻接矩阵看作"一步转移算子"，通路就是算子的复合；这条思路在随机游走与马尔可夫链里同样成立。

演练：布尔幂算可达性

把幂计数的代码动一个小手术，就从"数通路"切换到"判可达"，顺便预演第 4 章连通性判定的矩阵解法：

def boolean_reach(A, steps):
    """布尔幂：返回至多 steps 步内的可达矩阵"""
    R = A.astype(bool)                       # 第一步：直接邻居
    base = A.astype(bool)
    for _ in range(steps - 1):
        R = R | (R @ base)                   # 与=乘法 或=加法
    return R.astype(int)

print("至多两步可达：\n", boolean_reach(A, 2))
print("至多三步可达：\n", boolean_reach(A, 3))
# 继续迭代到矩阵不再变化，即为传递闭包（全量可达性）
​

输出里格子从零变一的节奏，正是"信息在图上逐层扩散"的轨迹——第 3 章广度优先的层次推进，在这里以矩阵的语言重演了一遍。同一件事的两种写法代价不同：布尔幂每轮一次矩阵乘，账单按顶点数的立方计；广度优先全图扫一遍只要顶点数加边数。这个对比是全册第一次"同一问题、多种计价"的正面教材，也再次提醒：表示法的选择从来不是纯口味问题，它直接决定哪类算法在你手里跑得动。

⚠️ 常见坑：带负权时用零表示"无边"会与"权为零的边"混淆，用无穷大表示又要小心溢出与初始化。工程上更稳妥的做法是把"无边"与"权"分开存（比如用可空字段或掩码），或者干脆换邻接表。

💡 关键直觉：矩阵把"结构"变成了"数字运算"。这让图的问题能借线性代数的刀——幂数通路、谱聚类看特征值、PageRank 求特征向量。看到矩阵别只想到存储，它还是台演算机。

方阵虽好，行囊有限。下一节给远征队换上轻装的档案袋：邻接表。