首页 > 试题广场 >

对于一个具有n个顶点的无向图,若采用邻接矩阵表示,则该矩阵的

[单选题]

对于一个具有n个顶点的无向图,若采用邻接矩阵表示,则该矩阵的大小是()

  • n
  • (n-1)^2
  • n-1
  • n^2
选D
【分析】

首先“邻接矩阵”是表示顶点之间相邻关系的矩阵。设G=(V,E)是一个图,其中V={v1,v2,…,vn} 。G的邻接矩阵是一个具有下列性质的n阶方阵:
①对无向图而言,邻接矩阵一定是对称的,而且主对角线一定为零(在此仅讨论无向简单图),副对角线不一定为0,有向图则不一定如此。
②在无向图中,任一顶点i的度为第i列(或第i行)所有非零元素的个数,在有向图中顶点i的出度为第i行所有非零元素的个数,而入度为第i列所有非零元素的个数。
③用邻接矩阵法表示图共需要n^2个空间,由于无向图的邻接矩阵一定具有对称关系,所以扣除对角线为零外,仅需要存储上三角形或下三角形的数据即可,因此仅需要n(n-1)/2个空间。
所以选择D
发表于 2019-04-09 18:35:38 回复(0)
更多回答
推荐
选D。
无向图的邻接矩阵是一个对称矩阵等同于一个二维数组,数组的大小为n2,一般用一个长度为N(N+1)/2的1维数组可以节省空间。
编辑于 2019-04-10 14:21:17 回复(0)
选D,顶点个数就是矩阵的行和列
发表于 2019-04-09 16:16:24 回复(0)
D,在邻接矩阵中,两两顶点间都有一个权值,但此权值可能是无穷大,表示两点间无路径。故需要n*n个数组空间来储存
发表于 2019-04-10 13:00:00 回复(0)