6.2.1 邻接矩阵

邻接矩阵 A[i][j] 表示 i 到 j 是否有边或边权。无向图矩阵对称；行和给度数。有向图第 i 行和给出度，第 j 列和给入度。空间 O(V²)，查边 O(1)，枚举邻居 O(V)，适合稠密图。

手工状态

顶点 A,B,C，边 AB、BC：矩阵为 0 1 0 / 1 0 1 / 0 1 0。A²[0][2]=1，表示长度2的走法 A-B-C 有1条。一般 A^k 的元素统计长度 k 的走法数。

结构与代码

加权图要区分“无边”和权值0，常用 INF 表示无边、对角线0。删除顶点需要移动整行整列或维护有效标志。

正确性依据

矩阵每个位置与一对有序顶点一一对应，所以查边常数时间；无向边在对称位置出现两次，统计边数需除2。

错解反馈

用0同时表示零权边和无边；无向图度数统计后再除2；只扫半矩阵却求有向图出度。

迁移训练

4点无向完全图矩阵有多少个1？答案12，因为6条边各出现两次。