若将 n 个顶点 e 条弧的有向图采用邻接表存储，则拓扑排序算法的时间复杂度是（）

复杂度分析 邻接表 拓扑排序

A. (O(n)) B. (O(n+e)) C. (O(n^2)) D. (O(n\log_2 n))

[tag_link]

正确答案：B

用邻接表实现 Kahn 拓扑排序时，初始化入度并让每个顶点至多入队、出队一次，共 O(n)；删除某顶点的出边时，每条弧只沿邻接表扫描一次，共 O(e)。因此总时间复杂度为 O(n+e)，选 B。若改用邻接矩阵，每次查找出边要扫描一整行，通常为 O(n²)。