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

18 查阅

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

A.

B.

C.

D.

参考答案:

B解析:具有n个节点的简单无向图的邻接矩阵是对称矩阵。对称矩阵关于主对角线对称,因此只需存储上三角或下三角部分即可。例如,只存储上三角中的元素aij,其特点是j≤i且1≤i≤n,对于上三角中的元素aij,它与对应的aij相等,因此当访问的元素在上三角时,直接去访问和它对应的下三角元素即可。由此可知,原来n×n个存储单元,现在只需要n(n+1)/2个存储单元。另外,由于简单无向图中没有自环,因此主对角线的元素无须存储,因此至少需要n(n-1)/2个存储单元。

软考中级