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

admin2012-06-26  41

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

选项 A、n(n+1)/2
B、n2/2
C、(n—1)(n+1)/2    D。n(n—1)/2

答案D

解析 简单无向图的邻接矩阵是对称的,且对角线元素均是0,故压缩存储只需存储下三角或是上三角(均不包括对角线)即可。故有(上三角形式):
    k=(n一1)+(n一2)+…+1+0=n2一(1+2+…+n)=n(n一1)/2。
转载请注明原文地址:https://kaotiyun.com/show/wfxi777K
0

相关试题推荐
最新回复(0)