单选题 设有向图具有n个顶点和e条边，如果用邻接表作为它的存储结构，则拓扑排序的时间复杂度为______。
  • A.O(n)
  • B.O(n+e)
  • C.O(n2)
  • D.O(n×e)
【正确答案】 B
【答案解析】[解析] 对于有n个顶点和e条边的有向图，建立各顶点的入度的时间复杂度为O(e)，建立入度为O的栈的时间复杂度为O(n)。在拓扑排序过程中，最多每个顶点进一次栈，入度减1的操作最多总共执行e次，可知总的时间复杂度为O(n+e)。