单选题
设有向图具有n个顶点和e条边,如果用邻接矩阵作为它的存储结构,则拓扑排序的时间复杂度为______。
A.O(nlog
2
e)
B.O(n+e)
C.O(n)
D.O(n
2
)
A
B
C
D
【正确答案】
D
【答案解析】
[解析] 采用邻接矩阵作为有向图的存储结构进行拓扑排序,需要输出每一个顶点,其时间复杂度为O(n)。在输出顶点后,要针对该顶点检测矩阵中对应的行,根据行中信息寻找与该顶点相关联的边,以便对这些边的入度减1,其时间复杂度为O(n)。因此,算法总的时间复杂度为O(n
2
)。
提交答案
关闭