图——邻接矩阵和邻接表存储的图的遍历的时间复杂度

用邻接矩阵构造图时，若存储的是一个无向图，则时间复杂度为O(n^2 + n*e)，其中，对邻接矩阵的初始化耗费的时间为O(n^2);对于DFS,BFS遍历来说，时间复杂度和存储结构有关：n表示有n个顶点，e表示有e条边。1.若采用邻接矩阵存储，时间复杂度为O(n^2);2.若采用邻接链表存储，建立邻接表或逆邻接表时，若输入的顶点信息即为顶点的编号，则时间复...

文章共232字 · 阅读需要大约1分钟

一键AI生成摘要，助你高效阅读

问答

傅华涛Fu

33081人浏览 · 2019-04-14 19:40:38

傅华涛Fu · 2019-04-14 19:40:38 发布

用邻接矩阵构造图时，若存储的是一个无向图，则时间复杂度为O(n^2 + n*e)，其中，对邻接矩阵的初始化耗费的时间为O(n^2);

对于DFS,BFS遍历来说，时间复杂度和存储结构有关：

n表示有n个顶点，e表示有e条边。

1.若采用邻接矩阵存储，

时间复杂度为O(n^2);

2.若采用邻接链表存储，建立邻接表或逆邻接表时，

若输入的顶点信息即为顶点的编号，则时间复杂度为O(n+e);

若输入的顶点信息不是顶点的编号，需要通过查找才能得到顶点在图中的位置，则时间复杂度为O(n*e);

GitCode 开源社区

旨在为数千万中国开发者提供一个无缝且高效的云端环境，以支持学习、使用和贡献开源项目。

更多推荐

【目标检测】目标检测的一些常用神经网络模型及方法

我的阶段性总结????文章目录1.概述1.2 目标检测的任务1.3 目标检测的分类2.R-CNN系列2.1 [R-CNN（Region with CNN features）](https://arxiv.org/pdf/1311.2524.pdf)2.2 [Fast R-CNN](https://www.cv-foundation.org/openaccess/content_iccv_2015/