A-A+

简单无向图的邻接矩阵是对称的可以对其进行压缩存储。若无向图G有n个结点其邻接矩阵为A[1

2022-08-06 18:22:02 问答库阅读 180 次

问题详情

简单无向图的邻接矩阵是对称的，可以对其进行压缩存储。若无向图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=n²一(1+2+…+n)=n(n一1)／2。