在用邻接表表示图时，拓扑排序算法时间复杂度为()。A.O(n)B.O(n+e)C.On×nD.O(n×n×n)
在用邻接表表示图时，拓扑排序算法时间复杂度为()。
A.O(n)
B.O(n+e)
C.On×n
D.O(n×n×n)
B.O(n+e)
C.On×n
D.O(n×n×n)
参考解析
解析：拓扑排序中每个顶点都需要出入栈(当用邻接表表示图时的执行次数为n)，然后把入度减1(当用邻接表表示图时的执行次数为e)，所以拓扑排序的时间复杂度为O(n+e)。
相关考题：
● 邻接矩阵和邻接表是图（网）的两种基本存储结构，对于具有 n个顶点、e条边的图， （59） 。（59）A. 进行深度优先遍历运算所消耗的时间与采用哪一种存储结构无关B. 进行广度优先遍历运算所消耗的时间与采用哪一种存储结构无关C. 采用邻接表表示图时，查找所有顶点的邻接顶点的时间复杂度为O(n*e)D. 采用邻接矩阵表示图时，查找所有顶点的邻接顶点的时间复杂度为O(n2)
采用邻接表存储的图的深度优先遍历算法类似于树的(22)，用邻接表存储的图的广度优先遍历算法类似于树的(23)，判断有向图是否存在回路，除了可以利用拓扑排序方法外，还可以利用(24)。A．中序遍历B．先序遍历C．后序遍历D．按层次遍历
设某有向无环图的顶点个数为n、弧数为e，那么用邻接表存储该图时，实现上述拓扑排序算法的函数TopSort的时间复杂度是(6)。若有向图采用邻接矩阵表示(例如，图4-1所示有向图的邻接矩阵如图4-3所示)，且将函数TopSort中有关邻接表的操作修改为针对邻接矩阵的操作，那么对于有n个顶点、e条弧的有向无环图，实现上述拓扑排序算法的时问复杂度是(7)。
对于具有n个顶点、6条边的图()。A.采用邻接矩阵表示图时，查找所有顶点的邻接顶点的时间复杂度为O(n2)B.进行广度优先遍历运算所消耗的时间与采用哪一种存储结构无关C.采用邻接表表示图时，查找所有顶点的邻接顶点的时间复杂度为O(n*e)D.进行深度优先遍历运算所消耗的时间与采用哪一种存储结构无关
填空题对用邻接矩阵表示的图进行任一种遍历时，其时间复杂度为（），对用邻接表表示的图进行任一种遍历时，其时间复杂度为（）。