简单无向图的邻接矩阵是对称的，可以对其进行压缩存储。若无向图G有n个结点，其邻接矩阵为A[1…n，1…n]，且压缩存储在B[1…k]，则k的值至少为( )。

admin2019-05-10 35

问题简单无向图的邻接矩阵是对称的，可以对其进行压缩存储。若无向图G有n个结点，其邻接矩阵为A[1…n，1…n]，且压缩存储在B[1…k]，则k的值至少为( )。

选项 A、n(n+1)／2
B、n²／2
C、(n～1)(n+1)／2
D、n(n一1)／2

答案D

解析简单无向图的邻接矩阵是对称的，且对角线元素均是0(因简单无向图不存在自己到自己的环路)，故压缩存储只须存储下三角或上三角(均不包括对角线)即可。故k值至少为1+2+3+…+(n一1)=n(n一1)／2；故选D。

转载请注明原文地址:https://kaotiyun.com/show/v6Ci777K

计算机408

相关试题推荐

随机试题

最新回复(0)