在用邻接表表示图时，拓扑排序算法时间复杂度为()。
- A.O(n)
- B.O(n+e)
- C.On×n
- D.O(n×n×n)
正确答案及解析
正确答案
B
解析
拓扑排序中每个顶点都需要出入栈(当用邻接表表示图时的执行次数为n)，然后把入度减1(当用邻接表表示图时的执行次数为e)，所以拓扑排序的时间复杂度为O(n+e)。
在用邻接表表示图时，拓扑排序算法时间复杂度为()。
拓扑排序中每个顶点都需要出入栈(当用邻接表表示图时的执行次数为n)，然后把入度减1(当用邻接表表示图时的执行次数为e)，所以拓扑排序的时间复杂度为O(n+e)。
