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