Question

在用邻接表表示图时,对图进行深度优先搜索遍历的算法的时间复杂度为()

为什么是O(n+e)，还有为什么用邻接矩阵表示时为O(n^2)

Answer 1

因为当相邻矩阵的大部分被破坏时，矩阵中的所有元素都需要扫并追踪到，且元素个数为n＾2，自然算法为O（n＾2）。

所以邻接表只存储边或弧，如果扫描邻接表，当然会得到O（n＋e）其中n是顶点的数量，e的边或弧的数量。

设有n个点，e条边

邻接矩阵：矩阵包含n＾2个元素，在算法中共n个顶点，对每个顶点都要遍历n次，所以时间复杂度为O（n＾2）。

邻接表：包含n个头结点和e个表结点，算法中对所有结点都要遍历一次，所以时间复杂度为O（n+e）顺便，对于广度优先算法的时间复杂度，也是这样。

扩展资料：

邻接表是图的最重要的存储结构之一，描述了图上的每个点。创建一个容器对于每一个图的顶点（n顶点n容器）和节点在第i个容器包含所有相邻顶点的顶点Vi。事实上，我们经常使用的邻接矩阵是一个邻接表的边集不离散化每一个点。

在有向图中，描述每个点与另一个节点连接的边(在a点->点B)。

在无向图中，描述每个点上的所有边（A点和B点的情况）

邻接表对应的图存储方法称为边集表。此方法将所有边存储在容器中。

参考资料来源：百度百科-邻接表

Answer 2

因为做拆邻接矩阵最坏时需要将矩阵中所有元素扫描完，元素个数是n^2个，自然算法就是O(n^2)
邻接表，只是存储了边或者弧，将邻接表扫描完就可友孙以了，时间复杂度自然就是O(n+e)了，n是顶点数，e的边或好胡链者弧的数量。

设有n个点，e条边

邻接矩阵：矩阵包含n^2个元素，在算法中共n个顶点，对每个顶点都要遍历n次，所以时间复杂度为O(n^2)。

邻接表：包含n个头结点和e个表结点，算法中对所有结点都要遍历一次，所以时间复杂度为O（n+e）顺便，对于广度优先算法的时间复杂度，也是这样。

扩展资料：

邻接表是图的一种最主要存储结构,用来描述图上的每一个点。对图的每个顶点建立一个容器（n个顶点建立n个容器），第i个容器中的结点包含顶点Vi的所有邻接顶点。实际上我们常用的邻接矩阵就是一种未离散化每个点的边集的邻接表。

在有向图中，描述每个点向别的节点连的边（点a->点b这种情况）。

在无向图中，描述每个点所有的边(点a-点b这种情况)

与邻接表相对应的存图方式叫做边集表，这种方法用一个容器存储所有的边。

参考资料来源：百度百科-邻接表

Answer 3

因为邻接矩阵最坏时需要将矩阵中所有元素扫描完，元素个数是n^2个，自然算法就是O(n^2)
邻接表，只是存储了边或者弧，将邻接表扫描完就可以了，时间复杂度自然就是O(n+e)了，n是顶点数，e的边或者弧的数量