若将n个顶点e条弧的有向图采用邻接表存储,则拓扑排序算法的时间复杂度是( )。

admin2017-08-16  1

问题 若将n个顶点e条弧的有向图采用邻接表存储,则拓扑排序算法的时间复杂度是(          )。

选项 A、O(n)
B、O(n+e)
C、O(n2)
D、O(ne)

答案B

解析 根据拓扑排序的规则,输出每个顶点的同时还要删除以它为起点的边,这样对各项点和边都要进行遍历,故拓扑排序的时间复杂度为O(n+e)。
转载请注明原文地址:https://kaotiyun.com/show/3DRi777K
0

最新回复(0)