GESP 八级 · GESP 202409 C++ 八级 第 2 题

对于一个具有 $n$ 个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小为（ ）。

邻接矩阵是n×n的方阵，matrix[i][j]表示顶点i到j是否有边（有权图存权值）。n个顶点需n²空间。

有向完全图边数为n(n-1)，无向完全图边数为n(n-1)/2。简单图不含自环和重边。

【考点】邻接矩阵｜图存储结构｜矩阵维度

考纲定位：本题考查数据结构模块中的图存储方式，属于 GESP 六级图论基础，八级常考邻接矩阵与邻接表对比。命题人卡住的是"无向图邻接矩阵是否因对称性而缩小"的直觉误区。

解题思维：邻接矩阵的本质是"每个顶点对应一行和一列"，n 个顶点必然构成 n×n 方阵。无论有向还是无向，矩阵维度只由顶点数决定；无向图的对称性仅影响矩阵内容（a[i][j]==a[j][i]），不改变行列数。行表示起点，列表示终点，因此直接锁定 n×n。

陷阱拆解：A 选项 n×(n/2) 源于"只存上三角"的存储优化误解，但题目问的是矩阵本身大小；C 选项 (n-1)×(n-1) 混淆了边数 n(n-1)/2 与矩阵维度；D 选项 (n+1)×(n+1) 误将顶点编号从 0 改为 1 后多出一行一列。最阴险的是对称性陷阱——学生看到无向图就下意识想"省一半空间"，却忽略矩阵定义。命题人最爱用"只存一半"这类绝对化表述误导，若改为有向图，矩阵仍是 n×n，只是不再对称。

反命题思维：若改为"邻接表中每个顶点的存储单元数"，答案变为 n（每个顶点存一个节点）；若改为"稠密无向图中 1 的个数"，答案变为 n(n-1)/2。若改为稀疏图，邻接矩阵仍为 n×n，只是 1 的个数减少。刷到类似题时先问：命题人想考矩阵维度还是对称性？