GESP 八级 · GESP 202312 C++ 八级 第 4 题

使用邻接矩阵表达 $n$ 个顶点的有向图，则该矩阵的大小为（ ）。

邻接矩阵是方阵，n个顶点对应n行n列，直接锁定B。

学生常把‘边数公式’和‘矩阵维度’搞混：有向完全图边数是n(n-1)，无向是n(n-1)/2，但题目问的是矩阵大小，不是边数；有的会误以为自环不该存而把对角线去掉，其实自环合法且矩阵仍是n×n；还有的被数字膨胀迷惑选A或C，记住有向图矩阵永远是对称性不存在的方阵。

考点定位

GESP八级《算法与数据结构》图论模块。命题人专门用‘有向图’三个字卡住七级只练过无向图的同学，制造记忆断层：无向图邻接矩阵对称，填一半就够了；有向图方向不同，每个格子都要独立存，所以必须是完整方阵。

概念拆解

邻接矩阵是一个二维数组matrix[i][j]，i和j都从1到n（或0到n-1）。matrix[i][j]=1表示存在有向边i→j，否则为0。n个顶点，每一行代表从该顶点出发的所有可能目标，一行有n个位置；n行就是n×n。这就是矩阵的大小。