用一个二维数组G存放图,G[i][j]表示节点i和结点j之间的边的情况(如有无边,边方向,权值大小等)。
遍历复杂度:O(n2) n为节点数目
(每个结点都需要走一次,下一次不会再走,当考察一个结点的时候,会考察跟这个结点相邻的所有结点,在邻接矩阵中,如何考察,就要看数组G的第i行。每个点需要考察一行)
每个结点V对应一个一维数组(Vector),里面存放从V连出去的边,边的信息包括另一顶点,还可能包含边权值
在边稀疏的情况下,遍历整个图的时间复杂度就比较好,是O(n+e),n为节点数目,e为边数目。
版权声明:本站所有资料均为网友推荐收集整理而来,仅供学习和研究交流使用。
工作时间:8:00-18:00
客服电话
电子邮件
admin@qq.com
扫码二维码
获取最新动态