校招刷题群
高效刷题 迎战校招
校招精选试题
近年面笔经面经群内分享
Java刷题群 前端刷题群 产品运营群
首页 > UI专业知识 > 色彩
题目

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

A.O(n)

B.O(n*n*n)

C.O(n*n)

D.O(n+e)

解答

正确答案是 D

若为避免重复检测入度为零的顶点,使用栈来保存所有入度为零的顶点。对有n个顶点和e条弧的有向图而言,建立求各顶点的入度的时间复杂度为O(e);建零入度顶点栈的时间复杂度为O(n);在拓扑排序过程中,若有向图无环,则每个顶点进一次栈,出一次栈,入度减一的操作在while循环中总共执行e次,所以总的时间复杂度为O(n+e)。

C 2条回复 评论
知乎

很基础的题,但还是要细心才能做对

发表于 2022-12-21 22:00:00
0 0
我真⁶⁶⁶₆₆₆⁶⁶⁶

拓扑排序结果不唯一,可以判断是否有环,针对有向图。时间复杂度为O(n+e),空间复杂度为O(n)。

发表于 2018-10-12 11:58:17
0 0