ncry.net
当前位置:首页 >> 稀疏图为什么用邻接表存储而不用邻接矩阵 >>

稀疏图为什么用邻接表存储而不用邻接矩阵

邻接表只需存储非零节点,而矩阵的话是不是要把所有节点的信息都保存上啊,而稀疏图的非零节点不多啊.所以存储效率高

邻接表有多种实现方式,比如最简单的动态链表,对于一个无向图,为每个节点建一个动态链表,储存的只是这个节点每个相邻的点,而在邻接矩阵中,对于每个节点需要把它与其他所有点的关系都表示出来(相邻为1,不相邻为0),空间复杂度明显是邻接矩阵大,至于查询两者各有千秋,如果只是查询两个点之间是否相邻,邻接矩阵当然更快,但如果是做dfs的话,找当前节点相邻的点,如果用邻接矩阵的话每次都要从1扫到n,如果用邻接表的话每次只需把当前节点邻接表后的点都取出来即可.

因为拓扑中两个结点只有一个单向边,用邻接表更节省空间,而且在实现拓扑排序时,查找下一个处理的结点,只需查找邻接表指针项为空的结点,查找平均复杂度为O(n)如果用邻接矩阵的话,必须从头开始扫描,平均复杂度为O(n^2)

这句话不对,邻接表和邻接矩阵,即可以存储无向图也可以存储有向图,稠密图适合用邻接矩阵,稀疏图适合用邻接表存储

稠密图一般用邻接矩阵,稀疏图一般用邻接表

将每一行的链表中的结点的邻接点下标(比如第i个头结点的链表中的弧结点中的信息为j),放到邻接矩阵中就是A[i][j]=1,如果结点还有权值则为权值,除了这些非0元素外,其他的都是0(如果有权图则其他的都是无穷大) 如果有向图的邻接表中有k个弧(边)结点,则邻接矩阵中就有k个1(或者权值)

对于n个顶点e条边的无向图,邻接表中除了n个头结点外,只有2e个表结点,空间效率为O(n+2e) 若为稀疏图(e<<n^2),则邻接表比邻接矩阵表示法O(n^2)省空间

如果是写代码的话,邻接矩阵肯定比邻接表好写,毕竟是数组实现;就时间复杂度上而言对于稀疏图用邻接表比较好,对于稠密图用邻接矩阵比较好;

wwfl.net | 3859.net | acpcw.com | gmcy.net | clwn.net | 网站首页 | 网站地图
All rights reserved Powered by www.ncry.net
copyright ©right 2010-2021。
内容来自网络,如有侵犯请联系客服。zhit325@qq.com