题目

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

错因

A

只数了顶点的处理次数（每个顶点入队、出队一次），忽视了边的处理代价。每条出边在某次顶点出队后都要被遍历一次（用于把目标顶点的入度减一）， 条边累计 ，不能漏掉。 只在没有任何边的极端情形成立。

C

把邻接表的复杂度套成了邻接矩阵的复杂度。用邻接矩阵存储时，要找一个顶点的所有邻居必须扫一整行， 个顶点共 次访问，于是拓扑排序退化到 。但题目明确说"邻接表"，访问出边只需走链表，无需逐项判断。

D

把"对每个顶点都遍历所有边"叠成了乘法，得到 。这是双重循环的"看似严谨"算法，但实际上拓扑排序中每条边只会在源点出队那次被处理一次——所有边总共 次，不是每个顶点 次。摊还后是加法 ，不是乘法。

总解析

拓扑排序（Kahn 算法）的标准实现：

1. 初始化：扫一遍邻接表，统计每个顶点的入度。— 访问每条边一次，。
2. 把所有入度为 0 的顶点入队。— 。
3. 重复以下过程，直到队列空：
   • 从队头取出顶点 ，输出 。— 出队 1 次 / 顶点，共 次。
   • 遍历 的所有出边，对每条边 ，把 的入度减 1；若减到 0 就把 入队。— 邻接表里 的出边链长度 = 的出度。

摊还分析：

• 第 3 步对所有顶点累计出队 次。
• 第 3 步对所有边累计遍历 次（每条边只在它的源点出队那次被访问，不会重复）。

总时间 。

对照其它存储方式：

存储方式	找一个顶点的所有出边	拓扑排序总复杂度
邻接表	走链表，
邻接矩阵	扫一行 个位置，

记忆口诀：邻接表 ↔ ""，邻接矩阵 ↔ ""。这套对应关系也适用于 DFS、BFS、Dijkstra（朴素版）等多数图算法。

最终答案是 B（）。