单选题
一个含有n个顶点和e条边的简单无向图,在其邻接矩阵存储结构中共有
(36)
个零元素。
A、
e
B、
2e
C、
n
2
-e
D、
n
2
-2e
【正确答案】
D
【答案解析】
[分析] 邻接矩阵反映顶点间邻接关系。设G=(V,E)是具有n个顶点的图,G的邻接矩阵M是一个n行n列的矩阵,并有若(i,j)或<i,j>∈E,则M[i][j]=1。否则M[i][j]=0。
由邻接矩阵的定义可知,无向图的邻接矩阵是对称的,即图中的一条边对应邻接矩阵的两个非零元素。因此在一个含有n个顶点和e条边的简单无向图的邻接矩阵中共有n
2
-2e个零元素。
提交答案
关闭