试题-在用邻接表表示图时,拓扑排序算法时间复杂度为()

题目

在用邻接表表示图时,拓扑排序算法时间复杂度为()

A.O(n)

B.O(n+e)

C.O(n*n)

D.O(n*n*n)

解答

正确答案是 B

增设一个存储入度的数组,一个用以组织入度为0的节点的栈S,则每个节点都需要入栈一次,一共n次,每个节点入度减1的操作一共e次,因此为O(n+e)

C 3条回复评论

老干妈拌面

用邻接表和用数组不一样，用数组好像是C

发表于 2018-10-13 11:46:18

岁月长歌

类似深度优先和广度优先，同时结合了入度的变化。

发表于 2018-10-13 11:46:04

橘子汽水

求各顶点入度的时间复杂度是O(e)，即边的个数。

建零入度顶点栈的时间复杂度是O(n)，即顶点的个数。

每个顶点都需要进一次栈，出一次栈，然后把入度减一。执行的总次数也是边的个数。

所以时间复杂度是O(n+e)。

发表于 2018-10-13 11:45:57