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

Question

简单无向图的邻接矩阵是对称的，可以对其进行压缩存储。若无向图G有n个结点，其邻接矩阵为A[1..n,1..n]，且压缩存储在B[1..k]中，则k的值至少为(40)。若按行压缩存储对称矩阵的上三角元素，则当n等于10时，边(V6,V3)的信息存储在 B[(41)]中。

A．

B．

C．

D．

Answer 1

正确答案：D
解析：具有n个结点的简单无向图的邻接矩阵是对称矩阵。对称矩阵关于主对角线对称，因此只需存储上三角或下三角部分即可。比如，我们只存储上三角中的元素aij，其特点是j≤i且1≤i≤n，对于上三角中的元素aij，它和对应的aij相等，因此当访问的元素在上三角时，直接去访问和它对应的下三角元素即可。这样，原米需要n*n个存储单元，现在只需要n(n+1)/2个存储单元了，由于简单无向图中没有自环，因此主对角线的元素无须存储，因此至少需要n(n-1)/2个存储单元。若按行压缩存储对称矩阵的上三角元素，则第1行需存储n-1个元素，第二行存储n-2个元素，第i行需存储n-i个元素，元素aij(1≤i≤n-1且ij≤n)存储在B[(i-1)n-i(i-1)/2+j-i]中，当n为10，与边(V6,V3)对应的矩阵元素为a3.6，即其信息存储在B[20]中。