一个含有n个顶点的连通且无环无向图在其邻接矩阵存储结构共有多少个零元素

2025-03-13 10:32:20
推荐回答(1个)
回答1:

原则上的确是n的平方,不过由于无向图的邻接矩阵是一个对称矩阵,只需要存储下三角或者上三角的元素,个数就是从1加到n,就是n(n+1)/ 2,不过题目问错了,这是压缩存储,是用一维数组存放,一般好像不叫矩阵
其实更精确地说,上面的数字个数是普通对称矩阵的,这个邻接矩阵的对角线一定为0,所以,只需要存储1 加到n-1,也就是n(n-1)/2就可以了