对于有n个顶点的无向图，怎样存储可以省一半空间
答案:1 悬赏:10 手机版
解决时间 2021-04-04 23:14
- 提问者网友：遮云壑
- 2021-04-04 13:26
对于有n个顶点的无向图，怎样存储可以省一半空间
最佳答案
- 五星知识达人网友：爱难随人意
- 2021-04-04 13:53
原则上的确是n的平方，不过由于无向图的邻接矩阵是一个对称矩阵，只需要存储下三角或者上三角的元素，个数就是从1加到n，就是n（n+1）/ 2，不过题目问错了，这是压缩存储，是用一维数组存放，一般好像不叫矩阵
其实更精确地说，上面的数字个数是普通对称矩阵的，这个邻接矩阵的对角线一定为0，所以，只需要存储1 加到n-1，也就是n(n-1)/2就可以了
其实更精确地说，上面的数字个数是普通对称矩阵的，这个邻接矩阵的对角线一定为0，所以，只需要存储1 加到n-1，也就是n(n-1)/2就可以了
我要举报
如以上问答信息为低俗、色情、不良、暴力、侵权、涉及违法等信息，可以点下面链接进行举报！
大家都在看
推荐资讯