题目

对于用邻接表表示图（包含n个定点e条边）时，拓扑排序算法时间复杂度为（）
（1）O(n)
（2）O(n＋e)
（3）O(n^2)
（4）O(n^3)

答案

（2）O(n＋e)

拓扑排序时，依次移除入度为 0 的顶点，并把该节点指向的节点的入度 - 1.

因此，访问了每个节点，对每个节点访问了其所有边。总的时间复杂度是 O(n + e).