必考题

考点

数据结构-图-图的属性

面5笔5

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

A.O(n)

B.O(n+e)

C.O(n*n)

D.O(n*n*n)

前往“校招VIP”小程序，刷题更快

最新校招难题刷题，快来进刷题群吧

解答

正确答案是 B

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

评论

老干妈拌面

2018-10-13 11:46:18

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

0 0

岁月长歌

2018-10-13 11:46:04

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

0 0

橘子汽水

2018-10-13 11:45:57

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

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

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

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

0 0